BZOJ1016 [JSOI2008]最小生成树计数-白红宇

BZOJ1016 [JSOI2008]最小生成树计数

阅读量：6614 次

发布时间：2019-06-24

本文共 2254 字，大约阅读时间需要 7 分钟。

题意：给定一张n<=100,m<=1000的无向图，另外同样权值的边不超过10条，求最小生成树的数目。

思路：首先我们将不同的权值从小到大分开考虑。

我们证明下面定理：一个无向图全部的最小生成树中某种权值的边的数目均同样。

開始时。每一个点单独构成一个集合。

首先仅仅考虑权值最小的边，将它们所有加入进图中，并去掉环，因为是所有尝试加入，那么仅仅要是用这样的权值的边可以连通的点，终于就一定能在一个集合中。

那么无论加入的是哪些边，终于形成的集合数都是一定的，且集合的划分情况一定同样。

那么真正加入的边数也是同样的。

由于每加入一条边集合的数目便降低1.

那么权值第二小的边呢？我们将之间得到的集合每一个集合都缩为一个点，那么权值第二小的边就变成了当前权值最小的边，也有上述的结论。

因此每一个阶段。加入的边数都是同样的。我们以权值划分阶段。那么也就意味着某种权值的边的数目是全然同样的。

于是我们考虑做法。

首先做一遍最小生成树看一下每种权值的边出现了几次。

若不能构成生成树输出0.

然后考虑每个阶段：从小到大处理每一种权值的边，状压枚举所有这样的权值的边，看这样的权值的边出现指定次数时是否能所有增加当前的森林。

若能，则这个阶段的数目+1.

那么答案就是每一个阶段的数目的乘积。

对于每个阶段，我们也能够不用暴力枚举，而用O(N^3)的Matrix-Tree定理求解行列式。若同样权值的边数过多的话就仅仅能用这样的方法了。

Code:(状态压缩)

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define N 110int n, m;struct Edge { int f, t, len; void read() { scanf("%d%d%d", &f, &t, &len); } bool operator < (const Edge &B) const { return len < B.len; }}E[1010];map
           
             M;int root[N], tmp[N];void reset() { for(int i = 1; i <= n; ++i) root[i] = i;}int find(int x) { int q = x, tq; for(; x != root[x]; x = root[x]); while(q != x) { tq = root[q]; root[q] = x; q = tq; } return x;}int count(int x) { int res = 0; for(; x; x -= x & -x) ++res; return res;}int _debug(int x) { return M[x];}#define Mod 31011int main() { scanf("%d%d", &n, &m); register int i, j, k; for(i = 1; i <= m; ++i) E[i].read(); sort(E + 1, E + m + 1); int intree = 0, ra, rb; reset(); for(i = 1; i <= m; ++i) { ra = find(E[i].f); rb = find(E[i].t); if (ra != rb) { ++M[E[i].len]; root[ra] = rb; if (++intree == n - 1) break; } } if (intree < n - 1) { puts("0"); return 0; } int S, res = 1, now; reset(); for(i = 1; i <= m; ) { for(j = i; E[j].len == E[j + 1].len; ++j); if (M[E[i].len]) { memcpy(tmp, root, sizeof root); now = 0; for(S = 1; S < (1 << (j - i + 1)); ++S) { if (count(S) != M[E[i].len]) continue; memcpy(root, tmp, sizeof tmp); bool ac = 1; for(k = i; k <= j; ++k) { if ((S >> (k - i)) & 1) { ra = find(E[k].f); rb = find(E[k].t); if (ra == rb) { ac = 0; break; } root[ra] = rb; } } if (ac) ++now; } res = res * now % Mod; memcpy(root, tmp, sizeof tmp); for(k = i; k <= j; ++k) { ra = find(E[k].f); rb = find(E[k].t); if (ra != rb) root[ra] = rb; } } i = j + 1; } printf("%d", res); return 0;}

转载地址：http://ezeso.baihongyu.com/

你可能感兴趣的文章