用php做网站要用构架吗,校园公共设施设计ppt,微信小程序模板源码,建设一个招聘网站的策划1016: [JSOI2008]最小生成树计数 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 6032 Solved: 2452[Submit][Status][Discuss]Description 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树#xff0c;而希望知道这个图中有多少个不同的最小生成树。… 1016: [JSOI2008]最小生成树计数 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 6032 Solved: 2452[Submit][Status][Discuss] Description 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树而希望知道这个图中有多少个不同的最小生成树。如果两颗最小生成树中至少有一条边不同则这两个最小生成树就是不同的。由于不同的最小生成树可能很多所以你只需要输出方案数对31011的模就可以了。 Input 第一行包含两个数n和m其中1n100; 1m1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行每行包含两个整数a, b, c表示节点a, b之间的边的权值为c其中1c1,000,000,000。数据保证不会出现自回边和重边。注意具有相同权值的边不会超过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 分析这道题还是比较坑的......首先我们要利用一条性质一个图的所有的最小生成树的同一边权的边的数目是相等的也就是说我们如果把最小生成树上的边权排序那么所有最小生成树的排列都是一样的。这个要怎么证明呢为了简便起见我们假设有2个不同的边权x1,x2x1x2,如果x1有2个x2有2个另一个最小生成树x1有3个x2有1个那么这是不可能的因为第二个最小生成树的边权和已经比第一个的小了如果第二个最小生成树x1有1个x2有3个这也不是最小生成树以此类推就能证明这个性质可能不是完全正确的但是明白这个结论就好了。 知道这个结论就比较好处理了。我们接下来要做的就是枚举每个边权满足要求的边数这里满足的要求是fa[x] ! fa[y],也就是构成最小生成树的要求因为有这个限制所以不能用组合数于是我们用dfs,看到了最后是不是达到了我们一开始求的那个最小生成树的边权的边的数目。也就是说我们以第一个最小生成树为模板后面的生成树的边权数与第一个相等的边的数目必须相等同时检测是不是满足要求就可以了。 有一个坑点这个图可能不能成为一棵树...... 还有一个坑点并查集不能用路径压缩不然dfs不好还原. 还有一个要注意的地方我们枚举完一个边权的边后要把这些边全部连起来为什么呢因为这为以后判断下一个边权的边是否满足条件奠定基础. #include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int mod 31011;int n, m, fa[1100],cnt,tot,l[1100],r[1100],sum[1100],ans 1;struct node
{int a, b, c;
}e[1010];bool cmp(node a, node b)
{return a.c b.c;
}int find1(int x)
{if (x fa[x])return x;return find1(fa[x]);
}int dfs(int x,int y,int z)
{int res 0;if (y r[x] 1){if (z sum[x])return 1;return 0;}int fx find1(e[y].a), fy find1(e[y].b);if (fx ! fy){fa[fx] fy;res dfs(x, y 1, z 1);res % mod;fa[fx] fx;}res dfs(x, y 1, z);res % mod;return res;
}int main()
{scanf(%d%d, n, m);for (int i 1; i n; i)fa[i] i;for (int i 1; i m; i)scanf(%d%d%d, e[i].a, e[i].b, e[i].c);sort(e 1, e 1 m, cmp);for (int i 1; i m; i){if (i 1)l[cnt] 1;elseif (e[i].c ! e[i - 1].c){r[cnt] i - 1;l[cnt] i;}int fx find1(e[i].a), fy find1(e[i].b);if (fx ! fy){fa[fx] fy;tot;sum[cnt];}}r[cnt] m;if (tot ! n - 1){printf(0\n);return 0;}for (int i 1; i n; i)fa[i] i;for (int i 1; i cnt; i){int tmp dfs(i,l[i],0);ans (ans * tmp) % mod;for (int j l[i]; j r[i]; j){int fx find1(e[j].a), fy find1(e[j].b);if (fx ! fy)fa[fx] fy;}}printf(%d\n, ans % mod);return 0;
} 转载于:https://www.cnblogs.com/zbtrs/p/7341547.html
