【题解】牛牛的航路
题意
给你一个n个节点m条边的图,求最大生成树,其中边权用组合数表示
题解
我们要求的是最大生成树,生成树算法中例如kruskal算法,只要将边权排序函数改为从大到小排序即可,但是由于边权是由组合数构成的那么一开始直接用杨辉三角进行组合数打表,打表的同时进行取模的话那么会丢失组合数原本大小的信息,所以我们不能用取完模后的组合数进行比较,那要怎么进行比较呢。观察组合数公式,由于是阶乘的除法,直接用大数存的话由于边较多会超时,所以我们可以转换一下,将阶乘的用对数表示,那就将乘法改为了对数加法,除法变为了对数减法,这样就可以进行组合数比较了。在后续记录组合数的和的时候可以用杨辉三角打表出来的组合数求和。
复杂度
时间复杂度为
空间复杂度为
代码
#include<bits/stdc++.h> using namespace std; const int N=1e3+5; const int M=1e6+5; const int mod=1e9+7; int F[N]; int C[N][N]; double L[N]; struct Edge{ int u,v,a,b,w; }edge[M]; int tol; void get_C() { C[0][0] = 1; for(int i=1;i<N;i++) { C[i][0] = 1; for(int j=1;j<=i;j++) C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod; } } void addedge(int u,int v,int a,int b) { edge[tol].u=u; edge[tol].v=v; edge[tol].a=a; edge[tol].b=b; edge[tol++].w=C[a][b]; } bool cmp(Edge a,Edge b) { return (L[a.a]-L[a.b]-L[a.a-a.b])>(L[b.a]-L[b.b]-L[b.a-b.b]); } int find(int x) { if(F[x]==-1) return x; else return F[x]=find(F[x]); } int Kruskal(int n) { memset(F,-1,sizeof(F)); sort(edge,edge+tol,cmp); int cnt=0; int ans=0; for(int i=0;i<tol;i++) { int u=edge[i].u; int v=edge[i].v; int w=edge[i].w; int t1=find(u); int t2=find(v); if(t1!=t2) { ans=(ans+w)%mod; F[t1]=t2; cnt++; } if(cnt==n-1)break; } if(cnt<n-1) return -1; else return ans; } int main() { get_C(); for(int i=1;i<N;i++) L[i]=L[i-1]+log(i); int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int u,v,a,b; scanf("%d%d%d%d",&u,&v,&a,&b); addedge(u,v,a,b); } printf("%d\n",Kruskal(n)); return 0; }