【题解】牛牛的航路

题意

给你一个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;
}
全部评论

相关推荐

07-09 18:33
门头沟学院 Java
这么逆天每年都有人去???&nbsp;填多益网申就是大型的服从性测试
鲁大牛:辅导员在群里发了这个公司我就申了一下。网申居然要写当场开摄像头写两篇不少于三百字的作文。太逆天了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务