luogu4208
2024-08-27 05:13:59
P4208 [JSOI2008]最小生成树计数
题目描述
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对31011的模就可以了。
输入格式
第一行包含两个数,n和m,其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。
接下来的m行,每行包含两个整数:a, b, c,表示节点a, b之间的边的权值为c,其中1<=c<=1,000,000,000。
数据保证不会出现自回边和重边。注意:具有相同权值的边不会超过10条。
输出格式
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
输入输出样例
输入 #1复制
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
输出 #1复制
8
说明/提示
说明 1<=n<=100; 1<=m<=1000;1<=ci<=1e9
sol:相同权值的最小生成树有一个很玄学的特点就是相同边权的边的数量时固定的而且作用也是相同的,然后相同的边的方案数可以爆搜出来,只要注意一点就是搜方案数时的并查集不能路径压缩,否则回溯的时候回挂掉
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
ll s=; bool f=; char ch=' ';
while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}
while(isdigit(ch)) {s=(s<<)+(s<<)+(ch^); ch=getchar();}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<) {putchar('-'); x=-x;}
if(x<) {putchar(x+''); return;}
write(x/); putchar((x%)+'');
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=,M=,Mod=;
int n,m,fa[N],lian[N];
struct Edge
{
int u,v,w;
}E[M];
inline bool cmpw(Edge p,Edge q) {return p.w<q.w;}
inline int gf(int x){return (fa[x]==x)?x:fa[x]=gf(fa[x]);}
inline int gl(int x){return (lian[x]==x)?x:gl(lian[x]);}
inline int dfs(int now,int end,int cnt)
{
if(now==end+)
{
if(cnt==) return ;
return ;
}
int ans=dfs(now+,end,cnt);
int fx=gl(E[now].u),fy=gl(E[now].v);
if(fx!=fy)
{
lian[fx]=fy;
ans+=dfs(now+,end,cnt-);
lian[fx]=fx;
}
return ans;
}
int main()
{
int i,j,tot=;
R(n); R(m);
for(i=;i<=m;i++)
{
R(E[i].u); R(E[i].v); R(E[i].w);
}sort(E+,E+m+,cmpw);
for(i=;i<=n;i++) fa[i]=i;
int ans=;
for(i=;i<=m;)
{
for(j=;j<=n;j++) lian[j]=j;
int oo=i,now=tot;
while(i<=m&&E[i].w==E[oo].w)
{
E[i].u=gf(E[i].u); E[i].v=gf(E[i].v); i++;
}
for(j=oo;j<i;j++)
{
int fx=gf(E[j].u),fy=gf(E[j].v);
if(fx!=fy)
{
tot++; fa[fx]=fy;
}
}
ans=1LL*ans*dfs(oo,i-,tot-now)%Mod;
}
if(tot==n-) Wl(ans);
else puts("");
return ;
}
最新文章
- 改变this指针的apply,call,bind的区别
- java的三大框架(一)
- C++引用和java引用的区别
- flash背景透明兼容ie火狐
- innodb_strict_mode
- 通过URL推送POST数据
- JQUERY的应用
- 如何学习.Net的步骤
- iOS合并静态库文件
- linux 进程间通信 之fifo
- 开源网络操作系统--VyOS
- SPRINGCLOUD 开发学习记录
- 集合源码分析[3]-ArrayList 源码分析
- mysql几种中间件对比
- windows下VMware-workstation中安装CentOS
- 读取Excel的部分问题
- 全栈框架mk-js
- Pandas分类
- linux查询进程 kill进程
- bootstrap-datetimepicker中设置中文