首页 > 代码库 > bzoj1016 [JSOI2008]最小生成树计数
bzoj1016 [JSOI2008]最小生成树计数
Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
Input
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
Sample Input
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
正解：$kruskal$+搜索/矩阵树定理。
这道题涉及到一些定理：
定理一：如果 $A, B$ 同为 $G$ 的最小生成树，且 $A$ 的边权从小到大为 $w(a_1), w(a_2), w(a_3), \cdots w(a_n)$，$B$ 的边权从小到大为 $w(b_1),w(b_2), w(b_3), \cdots w(b_n)$，则有 $w(a_i) = w(b_i)$。
证明：设$A, B$ 第一个不同的边的下标为 $i$，不妨设 $w(a_i) \le w(b_i)$，如果不存在这样的 $i$，无需证明。
情况一：$a_i$ 在 $B$ 中，为 $b_j$。那么显然有 $j>i$（否则 $i$ 不是第一个不同的边），则有 $w(a_i)\le w(b_i) \le w(b_j) = w(a_i)$，所以有 $w(a_i) = w(b_i) = w(b_j)$，所以可以调换 $b_i, b_j$ 的位置，$B$ 的权值排列不会改变， $A$ 与 $B$ 这样前 $i$ 条边均为相等，可以递归下去证明。
情况二：$a_i$ 不在 $B$ 中。考虑将 $a_i$ 加入 $B$，则形成了一个环，环中的权值 $v\le w(a_i)$（否则 $B$ 不是最小生成树），且一定有一条边 $b_j$ 不在 $B$ 中，此时仍有 $j>i$（否则 $i$ 不是第一个不同的边），所以有 $w(a_i)\le w(b_i) \le w(b_j) \le w(a_i)$，所以仍有 $w(a_i) = w(b_i) = w(b_j)$，可以将 $b_j$ 替换为 $a_i$，$B$ 的权值排列不会改变且仍为最小生成树，仍然调换 $b_i, b_j$ 的位置，$B$ 的权值排列仍会改变，这样 $A$ 与 $B$ 前 $i$ 条边均为相等，可以递归下去证明。这样换边不会有问题，因为 Kruskal 算法中唯一的状态就是连通性，我们没有改变其连通性，所以是可以递归证明的。
定理二：如果 $A, B$ 同为 $G$ 的最小生成树，如果 $A, B$ 都从零开始从小到大加边（$A$ 加 $A$ 的边，$B$ 加 $B$ 的边）的话，每种权值加完后图的联通性相同。
证明：归纳法证明，没有边时显然成立，假设对于权值小于 $v$ 的成立。考虑权值为 $v$ 的边，如果连通性不相同，必然存在 $u, v$ 两点间连通性不同，假设 $A$ 中 $u, v$ 联通，根据 $A, B$ 所有小于 $v$ 的边连通性相同，所以必然存在一条 $u\rightarrow v$ 权值为 $v$ 的边，而根据 Kruskal 算法的执行过程， $B$ 不可能不加这条边，所以两棵最小生成树 $A, B$ 各自权值小于等于 $v$ 的边仍然满足连通性相同。由归纳法可知定理二成立。
定理三：如果在最小生成树 $A$ 中权值为 $v$ 的边有 $k$ 条，用任意 $k$ 条权值为 $v$ 的边替换 $A$ 中的权为 $v$ 的边且**不产生环**的方案都是一棵合法最小生成树。
证明：根据之前的定理，其余的边造成的连通性是定的，权值和也是定的，那么选 $k$ 条不产生环一定能形成一棵树，而且权值与最小生成树的权值一样，故也是最小生成树。
——sengxian
于是我们可以先跑一遍最小生成树。然后对于每种权值的边，用搜索或矩阵树定理统计方案数（因为相同边权的边不超过10条所以爆搜能过）。然后乘法原理，直接把每种边的答案相乘就行了。
然而这题如果是搜索并查集不能写路径压缩。。坑了我好久。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath>10 #include <queue>11 #include <stack>12 #include <map>13 #include <set>14 #define rhl (31011)15 #define inf (1<<30)16 #define N (1010)17 #define il inline18 #define RG register19 #define ll long long20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)21 22 using namespace std;23 24 struct edge{ int u,v,w; }g[100010];25 struct node{ int l,r; }a[100010];26 27 int fa[100010],sum[100010],n,m,k,cnt,res,ans;28 29 il int gi(){30 RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();31 if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x;32 }33 34 il int cmp(const edge &a,const edge &b){ return a.w<b.w; }35 36 il int find(RG int x){ return fa[x]==x ? fa[x] : find(fa[x]); }37 38 il void dfs(RG int cnt,RG int x,RG int v){39 if (x>a[cnt].r){ if (v==sum[cnt]) res++; return; }40 dfs(cnt,x+1,v); RG int p=find(g[x].u),q=find(g[x].v);41 if (p!=q) fa[p]=q,dfs(cnt,x+1,v+1),fa[p]=p,fa[q]=q;42 return;43 }44 45 il void work(){46 n=gi(),m=gi();47 for (RG int i=1;i<=m;++i) g[i].u=gi(),g[i].v=gi(),g[i].w=gi();48 sort(g+1,g+m+1,cmp); for (RG int i=1;i<=n;++i) fa[i]=i; cnt=0;49 for (RG int i=1;i<=m;++i){50 if (g[i].w!=g[i-1].w) cnt++;51 if (!a[cnt].l) a[cnt].l=i; a[cnt].r=i;52 RG int p=find(g[i].u),q=find(g[i].v);53 if (p!=q) fa[p]=q,k++,sum[cnt]++;54 }55 if (k!=n-1){ printf("0"); return; }56 for (RG int i=1;i<=n;++i) fa[i]=i; ans=1;57 for (RG int i=1;i<=cnt;++i){58 res=0,dfs(i,a[i].l,0),(ans*=res)%=rhl;59 for (RG int j=a[i].l;j<=a[i].r;++j){60 int p=find(g[j].u),q=find(g[j].v);61 if (p!=q) fa[p]=q;62 }63 }64 printf("%d",ans); return;65 }66 67 int main(){68 File("counttree");69 work();70 return 0;71 }
bzoj1016 [JSOI2008]最小生成树计数