【HDU 4408】Minimum Spanning Tree(最小生成树计数)
生成 HDU 最小 Tree 计数 minimum
2023-09-11 14:19:25 时间
Problem Description
XXX is very interested in algorithm. After learning the Prim algorithm and Kruskal algorithm of minimum spanning tree, XXX finds that there might be multiple solutions. Given an undirected weighted graph with n (1<=n<=100) vertexes and m (0<=m<=1000) edges, he wants to know the number of minimum spanning trees in the graph.
Input
There are no more than 15 cases. The input ends by 0 0 0.
For each case, the first line begins with three integers --- the above mentioned n, m, and p. The meaning of p will be explained later. Each the following m lines contains three integers u, v, w (1<=w<=10), which describes that there is an edge weighted w between vertex u and vertex v( all vertex are numbered for 1 to n) . It is guaranteed that there are no multiple edges and no loops in the graph.
For each case, the first line begins with three integers --- the above mentioned n, m, and p. The meaning of p will be explained later. Each the following m lines contains three integers u, v, w (1<=w<=10), which describes that there is an edge weighted w between vertex u and vertex v( all vertex are numbered for 1 to n) . It is guaranteed that there are no multiple edges and no loops in the graph.
Output
For each test case, output a single integer in one line representing the number of different minimum spanning trees in the graph.
The answer may be quite large. You just need to calculate the remainder of the answer when divided by p (1<=p<=1000000000). p is above mentioned, appears in the first line of each test case.
The answer may be quite large. You just need to calculate the remainder of the answer when divided by p (1<=p<=1000000000). p is above mentioned, appears in the first line of each test case.
Sample Input
5 10 12
2 5 3
2 4 2
3 1 3
3 4 2
1 2 3
5 4 3
5 1 3
4 1 1
5 3 3
3 2 3
0 0 0
Sample Output
4
Source
Recommend
zhoujiaqi2010 | We have carefully selected several similar problems for you: 5831 5830 5829 5828 5827
题意是给定n个点,m条边的无向图,求最小生成树的个数对p取模。
用kruscal计算最小生成树时,每次取连接了两个不同联通块的最小的边。也就是先处理d1条c1长度的边,再处理d2条c2长度的边。长度相同的边无论怎么选,最大联通情况都是固定的。 分别对ci长度的边产生的几个联通块计算生成树数量再乘起来,然后把这些联通块缩点,再计算ci+1长度的边。
生成树计数用Matrix-Tree定理,上一篇是无重边的,这题的缩点后是会产生重边的,Matrix-tree也适用:
Kirchhoff矩阵任意n-1阶子矩阵的行列式的绝对值就是无向图的生成树的数量。
Kirchhoff矩阵的定义是度数矩阵-邻接矩阵。
1、G的度数矩阵D[G]:n*n的矩阵,Dii等于Vi的度数,其余为0。
2、G的邻接矩阵A[G]:n*n的矩阵, Vi、Vj之间有边直接相连,则 Aij=ij之间的边数,否则为0。
并查集fa[i]是当前长度之前,节点所属的联通块,ka[i]是当前长度的边连接后它在的联通块。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long ll; const int N=101; const int M=1001; ll n,m,p,ans; vector<int>gra[N]; struct edge{ int u,v,w; }e[M]; int cmp(edge a,edge b){ return a.w<b.w; } ll mat[N][N],g[N][N]; ll fa[N],ka[N],vis[N]; ll det(ll c[][N],ll n){ ll i,j,k,t,ret=1; for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]%=p; for(i=0; i<n; i++){ for(j=i+1; j<n; j++) while(c[j][i]){ t=c[i][i]/c[j][i]; for(k=i; k<n; k++) c[i][k]=(c[i][k]-c[j][k]*t)%p; swap(c[i],c[j]); ret=-ret; } if(c[i][i]==0) return 0L; ret=ret*c[i][i]%p; } return (ret+p)%p; } ll find(ll a,ll f[]){ return f[a]==a?a:find(f[a],f); } void matrix_tree(){//对当前长度的边连接的每个联通块计算生成树个数 for(int i=0;i<n;i++)if(vis[i]){//当前长度的边连接了i节点 gra[find(i,ka)].push_back(i);//将i节点压入所属的联通块 vis[i]=0;//一边清空vis数组 } for(int i=0;i<n;i++) if(gra[i].size()>1){//联通块的点数为1时生成树数量是1 memset(mat,0,sizeof mat);//清空矩阵 int len=gra[i].size(); for(int j=0;j<len;j++) for(int k=j+1;k<len;k++){//构造这个联通块的矩阵(有重边) int u=gra[i][j],v=gra[i][k]; if(g[u][v]){ mat[k][j]=(mat[j][k]-=g[u][v]); mat[k][k]+=g[u][v];mat[j][j]+=g[u][v]; } } ans=ans*det(mat,gra[i].size()-1)%p; for(int j=0;j<len;j++)fa[gra[i][j]]=i;//缩点 } for(int i=0;i<n;i++) { gra[i].clear(); ka[i]=fa[i]=find(i,fa); } } int main(){ while(scanf("%lld%lld%lld",&n,&m,&p),n){ for(int i=0;i<m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--;v--; e[i]=(edge){u,v,w}; } sort(e,e+m,cmp); memset(g,0,sizeof g); ans=1; for(ll i=0;i<n;i++)ka[i]=fa[i]=i; for(ll i=0;i<=m;i++){//边从小到大加入 if(i&&e[i].w!=e[i-1].w||i==m)//处理完长度为e[i-1].w的所有边 matrix_tree();//计算生成树 ll u=find(e[i].u,fa),v=find(e[i].v,fa);//连的两个缩点后的点 if(u!=v)//如果不是一个 { vis[v]=vis[u]=1; ka[find(u,ka)]=find(v,ka);//两个分量在一个联通块里。 g[u][v]++,g[v][u]++;//邻接矩阵 } } int flag=1; for(int i=1;i<n;i++)if(fa[i]!=fa[i-1])flag=0; printf("%lld\n",flag?ans%p:0);//注意p可能为1,这样m=0时如果ans不%p就会输出1 } }
相关文章
- yii2:frontend/frontactoin curl生成
- 第三百二十节,Django框架,生成二维码
- 重命名和重定向RF执行生成的output文件
- 机器学习笔记:常用数据集之scikit-learn生成分类和聚类数据集
- SAP云平台CloudFoundry环境里新建SAP UI5应用后,自动生成了哪些组件
- SAP OData的CSRF token在ABAP Netweaver服务器上是怎么生成的
- Angular Component模板里的元素,运行时如何被生成并插入到DOM tree中
- 【hdu 2108】Shape of HDU
- 二十行代码实现JavaScript在本地生成pdf文件
- 利用深度学习生成数据的时间序列预测(Matlab代码实现)
- 数学建模学习(18):图与网络模型之图的最小生成树问题详细讲解,超详细!
- 高性能Web动画和渲染原理系列(5)合成层的生成条件和陷阱
- Makefile 书写规则 规则举例 规则的语法 通配符 文件搜寻 伪目标 多目标 静态模式 自动生成依赖性
- poj 3307 Smart Sister 打表解因子生成数问题
- 系统中生成编号/单号问题的实现方案讨论
- MATLAB | 二维波函数坍缩算法随机地图生成
- Audition生成扫频信号(四十)
- Qt生成和调用动态库dll,和静态库.a(windows和linux通用)