P4208 [JSOI2008]最小生成树计数

2021-02-16 16:22

阅读：703

标签：答案 cpp for == 计数 char dfs read print

题目描述

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对\(31011\)的模就可以了。

题解

容易想到对于边权相同的那些边，选出来的边数是一定的，所以最终答案其实就是各个边权相同的部分的方案数的乘积，用并查集维护\(dfs\)即可，注意：由于有撤销操作，所以不能进行路径压缩。

#include 
#include 
#include 
using namespace std;
const int N = 1005;
const int mod = 31011;
int n, m, fa[N], cnt, tot, sum, ans = 1, now;
struct node{int x, y, z;}a[N];
struct data{int l, r, val;}e[N];
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while(ch  ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
	while(ch >= ‘0‘ && ch

P4208 [JSOI2008]最小生成树计数

标签：答案 cpp for == 计数 char dfs read print

原文地址：https://www.cnblogs.com/Sunny-r/p/12966803.html

上一篇：可想实现一个自己的简单jQuery库？(四)

下一篇：【API】Windows 获取电池电量信息

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：P4208 [JSOI2008]最小生成树计数
文章链接：http://soscw.com/index.php/essay/56177.html

亲，登录后才可以留言！

P4208 [JSOI2008]最小生成树计数

题目描述

题解

评论

热门文章

推荐文章

最新文章

置顶文章