DATE #:20240817
ITEM #:DOC
WEEK #:SATURDAY
DAIL #:捌月拾肆
TAGS
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2610346970&auto=0&height=66" width="330"></iframe> < BGM = "快哉风 -- 黄金玉米王" > < theme = oi-language > < theme = oi-graph theory > < [空] > < [空] >取次花丛懒回顾，半缘修道半缘君 -- 元稹《离思五首·其四》
[P4208 [JSOI2008] 最小生成树计数]([P4208 JSOI2008] 最小生成树计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
[JSOI2008] 最小生成树计数
题目描述
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两棵最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对 \(31011\) 的模就可以了。
输入格式
第一行包含两个数，\(n\) 和 \(m\)，其中 \(1 \le n \le 100\)，\(1 \le m \le 1000\)，表示该无向图的节点数和边数。每个节点用 \(1 \sim n\) 的整数编号。
接下来的 \(m\) 行，每行包含两个整数：\(a,b,c\)，表示节点 \(a,b\) 之间的边的权值为 \(c\)，其中 \(1 \le c \le 10^9\)。
数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过 \(10\) 条。
输出格式
输出不同的最小生成树有多少个。你只需要输出数量对 \(31011\) 的模就可以了。
样例 #1
样例输入 #1
4 6 1 2 1 1 3 1 1 4 1 2 3 2 2 4 1 3 4 1样例输出 #1
8提示
数据范围及约定
对于全部数据，\(1 \le n \le 100\)，\(1 \le m \le 1000\)，\(1\leq c_i\leq 10^9\)。
先引入一个引理：
对于一个图的最小生成树，每个边权的边出现的次数是一样的
证明：模拟kruskal的过程，我们在给边排序时，交换同权的边并没有什么影响
那么我们先求解出最小生成树，并依次计算权值
考虑，当我们要加入权值为\(i\)的若干条边时，
前面加入的边已经使其变成了几个联通块，只要考虑用权值为\(i\)的边跑一次生成树数量即可，
之后对每个边权都依次操作
//2024.8.17
//by white_ice
//[JSOI2008] 最小生成树计数 |P4208
#include<bits/stdc++.h>
//#include"need.cpp"
using namespace std;
#define itn int
constexpr itn oo = 1003;
constexpr int mod = 31011;
struct nod{int x,y,z;}st[oo],sp[oo];
int cmp(nod a,nod b){return a.z<b.z;}
int n,m,t;
itn fa[oo],d[oo],c[oo],cnt,out,xx,yy;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
__inline void dfs(int now,int k,int x){
if (now>sp[x].y){
if (k==d[x]) cnt++;
return void();
}
int p[101];
for (int i=1;i<=n;i++) p[i]=fa[i];
xx=find(st[now].x);yy=find(st[now].y);
if (xx!=yy){
fa[xx]=yy;
dfs(now+1,k+1,x);
}
for (int i=1;i<=n;i++) fa[i]=p[i];
dfs(now+1,k,x);
}
main(void){
//fre();
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i=1;i<=m;i++)cin >> st[i].x >> st[i].y >> st[i].z;
sort(st+1,st+1+m,cmp);
for (int i=1;i<=n;i++)fa[i]=i;
st[0].z=-INT_MAX;t=0;
for (int i=1;i<=m;i++){
if (st[i].z==st[i-1].z){sp[t].y++;c[i]=t;}
else {t++;sp[t].x=i;sp[t].y=i;c[i]=t;}
}
cnt=0;
for (int i=1;i<=m;i++){
xx=find(st[i].x);yy=find(st[i].y);
if (xx!=yy){
fa[xx]=yy;
d[c[i]]++;
cnt++;
}
if (cnt==n-1) break;
}
if (cnt!=n-1) {printf("0");exit(0);}
for (int i=1;i<=n;i++) fa[i]=i;
out=1;
for (int i=1;i<=t;i++)
if (d[i]>0){
cnt=0;
dfs(sp[i].x,0,i);
out=(out*cnt)%mod;
for (int j=sp[i].x;j<=sp[i].y;j++){
xx=find(st[j].x);yy=find(st[j].y);
if (xx!=yy)fa[xx]=yy;
}
}
cout << out << flush;
exit (0);
}