_WA自动机的blog

过期高中生。

BZOJ1016

发表于 更新于 分类于 ， 阅读次数： Valine：

大意：

给你一个联通无向图，求其最小生成树的个数。答案对31011取模。（鬼知道为啥是这个数）

分析：

这道题有个很有趣也很奇妙的结论...

1.对于一个无向连通图来说，它的所有最小生成树中，相等边权的边的数量都是相等的，且在去掉这些相等边权的边之后，图的连通性也是相同的。

这个结论怎么证明呢？大胆猜想，无需证明

这里给出一个简单证明感性理解：考虑kruskal的过程,不妨把加入相同权值的边看做一个“阶段”。每次加边都是加到加入图中会形成环为止。然后进入下一个阶段。那么，把前面已经被更小权值的边联通的联通块看做一些点，则我们就是在这些点之间随便连边。如果形成环，我们选择不加入这条边还是从环上删除一条边并加入这条边，对连通性和生成树中该种边权边的条数显然都没有影响。所以，上述结论成立。

有了这个结论，我们重新来审视这道题。我们要求最小生成树的个数。不妨仍然把相同权值的边看成阶段。根据乘法原理，我们要求的答案就是每个阶段连边的方案数之积。那么，我们先求一遍最小生成树。并得到一种方案。然后再次跑一遍kruskal，在每个阶段，将原先最小生成树中除了该阶段的边的其他边连进这张图，然后将图进行缩点（这个可以用并查集实现）然后在缩点后的新图上，加入这个阶段的所有边。此时求新图的生成树方案数，每一种方案都对应着原图中这个阶段的一种加边方案。采用矩阵树定理求生成树就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using std::sort;
using std::swap;
using std::fabs;

const int P=31011;
const int maxn=(1e3+100)*2;
const double eps=1e-6;

bool used[maxn];

namespace MST
{
    int fa[maxn];
    int u[maxn],v[maxn],w[maxn],r[maxn],tot;
    long double K[maxn][maxn];
    inline int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
    inline void add(int _u,int _v,int _w){u[++tot]=_u,v[tot]=_v,w[tot]=_w;}
    struct cmp{bool operator() (const int a,const int b){return w[a]<w[b];}};
    inline long double determinant(long double (*A)[maxn],int n)
    {
        for (int i=1,c=1,j;i<=n;++i)
        {
            for (j=c;j<=n && fabs(A[j][i])<eps;++j);
            if (j==n+1) continue;
            for (int k=1;k<=n;++k) swap(A[c][k],A[j][k]);
            for (int j=c+1;j<=n;++j)
                if (fabs(A[j][i])>eps)
                {
                    long double t=A[j][i]/A[c][i];
                    for (int k=i;k<=n;++k)
                        A[j][k]-=A[c][k]*t;
                }
            ++c;
        }
        long double ans=1;
        for (int i=1;i<=n;++i) ans*=A[i][i];
        return fabs(ans);//这里要取绝对值
    }
    inline void Kruskal(int n,int m)
    {
        for (int i=1;i<=n;++i) fa[i]=i;
        for (int i=1;i<=m;++i) r[i]=i;
        sort(r+1,r+m+1,cmp());
        for (int i=1;i<=m;++i)
        {
            int x=r[i];
            if (find(u[x])!=find(v[x]))
            {
                fa[find(u[x])]=find(v[x]);
                used[x]=true;
            }
        }
    }
    int index[maxn];
    inline void Add_edge(int idx)
    {
        int x=index[find(u[idx])],y=index[find(v[idx])];
        ++K[x][x];++K[y][y];
        --K[x][y];--K[y][x];
    }
    inline void merge(int idx)
    {
        if (find(u[idx])!=find(v[idx]))
            fa[find(u[idx])]=find(v[idx]);
    }
    inline int Build_Graph(int n,int m,int L,int R)
    {
        int tot=0;
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                K[i][j]=0;
        for (int i=1;i<=n;++i) fa[i]=i;
        for (int i=1;i<=m;++i)
            if (used[r[i]] && (i<L || i>R)) merge(r[i]);
        memset(index,0,sizeof(index));
        for (int i=1;i<=n;++i) if (!index[find(i)]) index[find(i)]=++tot;
        for (int i=L;i<=R;++i) Add_edge(r[i]);
        return tot;
    }
    inline int Kruskal_cal(int n,int m)
    {
        int ans=1;
        for (int L=1,R=1;R<=m;L=R)
        {
            bool ok=false;
            while (w[r[L]]==w[r[R]] && R<=m)
                if (used[r[R++]]) ok=true;
            if (!ok) continue;
            int tot=Build_Graph(n,m,L,R-1);
            ans=((long long)ans*(int)std::round(determinant(K,tot-1)))%P;
        }
        return ans;
    }
} // Kruskal

int main()
{
    // freopen("1016/1.in","r",stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1,u,v,w;i<=m;++i)
        scanf("%d%d%d",&u,&v,&w),MST::add(u,v,w);
    MST::Kruskal(n,m);
    printf("%d",MST::Kruskal_cal(n,m));
}