【bzoj1016】 JSOI2008—最小生成树计数
2024-09-15 23:56:24
http://www.lydsy.com/JudgeOnline/problem.php?id=1016 (题目链接)
题意
求图的最小生成树计数。
Solution
%了下题解,发现要写矩阵树,150++的程序什么鬼。于是就蒯了hzwer的简便方法。
将边按照权值大小排序,将权值相同的边分到一组,统计下每组分别用了多少条边。然后对于每一组进行dfs,判断是否能够用这一组中的其他边达到相同的效果。最后把每一组的方案数相乘就是答案。
注意并查集不要压缩路径,不然的话不好回溯。
代码
// bzoj1016
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define MOD 31011
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
int getint() {
int f=1,x=0;char ch=getchar();
while (ch<='0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=1010;
struct edge {int u,v,w;}e[maxn<<2],a[maxn];
int fa[maxn],sum,n,m,cnt,tot; bool cmp(edge a,edge b) {
return a.w<b.w;
}
int find(int x) {
return fa[x]==x ? x : find(fa[x]);
}
void dfs(int x,int now,int k) {
if (now==a[x].v+1) {
if (k==a[x].w) sum++;
return;
}
int r1=find(e[now].u),r2=find(e[now].v);
if (r1!=r2) {
fa[r1]=r2;
dfs(x,now+1,k+1);
fa[r1]=r1,fa[r2]=r2;
}
dfs(x,now+1,k);
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
for (int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m,cmp);
for (int i=1;i<=m;i++) {
if (e[i].w!=e[i-1].w) {a[++cnt].u=i;a[cnt-1].v=i-1;}
int r1=find(e[i].u),r2=find(e[i].v);
if (r1!=r2) {fa[r1]=r2;a[cnt].w++;tot++;}
}
a[cnt].v=m;
if (tot!=n-1) {printf("0");return 0;}
for (int i=1;i<=n;i++) fa[i]=i;
int ans=1;
for (int i=1;i<=cnt;i++) {
sum=0;
dfs(i,a[i].u,0);
ans=(ans*sum)%MOD;
for (int j=a[i].u;j<=a[i].v;j++) {
int r1=find(e[j].u),r2=find(e[j].v);
if (r1!=r2) fa[r1]=r2;
}
}
printf("%d",ans);
return 0;
}
最新文章
- TextView属性android:ellipsize=";marquee";不生效的解决办法
- sass/less/stylus css编译
- 自己写的基于bootstrap风格的弹框插件
- 基数树(radix tree)
- sql临时表和表变量
- Daily Scrum 11.11
- Android中的pix,sp,dp相关概念
- python 简单谈谈“类”
- linux基础知识1
- ural1519插头DP
- CvIntHaarClassifier
- ArcGIS API for JavaScript 4.2学习笔记[15] 弹窗内容的格式与自定义格式
- 联网请求数据:Android篇
- SVN服务器搭建及使用
- xpath获取一个标签下的多个同级标签
- Java读文件
- RecyclerView通用适配器
- SNMP学习笔记之SNMP树形结构介绍
- Kibana 基础入门
- Pelican+Github博客搭建详细教程
热门文章
- Unity 2D Sprite Lighting
- java 15-1 Collection集合的概述以及小功能介绍
- CSS3中的字体rem
- linux如何挂载windows下的共享文件
- immutability-javascript
- Linux中查看各文件夹大小命令du -h --max-depth=1
- HttpClient通过Post上传文件(转)
- JS原型-语法甘露
- “插件(application/x-vlc-plugin)不受支持”NPAPI和PPAPI的问题
- 通过HttpClient来调用Web Api接口~续~实体参数的传递