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,0 00。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。

Output

输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。

Sample Input

4 6 1 2 1 1 3 1 1 4 1 2 3 2 2 4 1 3 4 1 Sample Output

8 首先需要一个结论，对于一个图的不同最小生成树，每种方案所包含的每种权值的边的数量一定一致。换句话说，把每种方案包含的所有边的边权都写下来，写出来的序列一定都一样。关于这个结论的说明放在最后。 这样的话，可以先做一遍kruskal，记下每种边权的使用次数，然后对于每种边权进行dfs，判断有多少种合法的组合方式【一种方案合法意味着：1.加入每条边时，边的两端点一定属于不同的并查集，也就是仍然要符合kruskal的要求。2.加入的总边数等于开始统计的使用次数。第一条要求也就决定了不能用组合数进行计算，只能dfs，而因为相同边权的边不超过10，再加上一些最简单的剪枝，运行速度很快。】，然后用乘法原理即可。 注意： 1.dfs的时候要回溯，所以这里的并查集不能进行路径压缩。 2.处理完每种边之后要把这些边加上去，这才是kruskal的过程。 3.考虑图不连通，即不存在最小生成树的情况。 最后说一下原理。考虑kruskal的过程，只有当这一权值的边全部考虑之后才会考虑权值比他大的边。举个最简单的例子，假设有两种方案，第一种方案有边x1，x4，第二种有边x2，x3，且x1< x2< x3< x4。因为一条边只能连接两个连通块，那么x2，x3中一定有一个能起到x4的作用，那么这个能起作用的点和x1组成的方案才是最小生成树。 既然这样，不同的方案从何而来呢？来自于相同的权值的边，在排序后的顺序不同，而他们又起着相同的作用（也就是连接相同的联通块）【因为如果作用不一样的话，他们应该都被纳入方案】，那么先考虑这个和先考虑那个就会得出不同的方案。 于是，我们对每一组权值相同的边，知道了他们总的使用次数以后，进行暴力的枚举统计方案数。因为我们知道，不管怎么选，最后的结果，也就是给后面带来的影响，都是相同的【因为如果影响不同，那么就不应该现在从中挑选，当初kruskal的时候应该都选进来。】 那么这种做法，和直接暴力枚举的区别就显现了。暴力枚举是整个的指数级，而这种做法是把总数分成很多小块，在每一块里暴力枚举，最后的复杂度是每一块的指数相加，自然小了很多。

相当于我先用kruskal做出我的最小生成树 然后记录下一共使用了多少种权值 因为我是排好序的所以我给每个权值分段 并且记录下我每种权值都用了多少 然后根据上面的证明 我权值连接的应该都是相同的联通块才行 每次做完一种权值后就给他们连起来 （ps：造成的效果是一样的）所以随便连就可以了

#include#include#define#define#defineusing namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int x,y,z;}data[M];struct node1{ int num,l,r;}group[M];inline bool cmp(node a,node b){return a.zgroup[id].r){if (now==group[id].num) ans1++;return;} dfs(id,step+1,now); int xx=find(data[step].x),yy=find(data[step].y); if (xx!=yy){ fa[xx]=yy;dfs(id,step+1,now+1); fa[xx]=xx;fa[yy]=yy; }}int main(){ freopen("bzoj1016.in","r",stdin); n=read();m=read(); for (int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); data[i].x=x;data[i].y=y;data[i].z=z; } sort(data+1,data+m+1,cmp);int g=0,cnt=0; for (int i=1;i<=n;++i) fa[i]=i; for (int i=1;i<=m;++i){ if (data[i].z!=data[i-1].z) group[g].r=i-1,group[++g].l=i; int xx=find(data[i].x),yy=find(data[i].y); if (xx!=yy){ ++cnt;group[g].num++;fa[xx]=yy; } }group[g].r=m; if (cnt

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。