（C语言）对于下图，利用最小生成树算法，计算连通所有节点的最小代价

（C语言）对于下图，利用最小生成树算法，计算连通所有节点的最小代价

可以参考下文：
https://blog.csdn.net/weixin_43718786/article/details/84147573

希望帮到你

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000,MAXM=100000,inf=1e9;
struct Edge
{
    int v,c,f,nx;
    Edge() {}
    Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
void init(int _n)
{
    N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);
}
void link(int u,int v,int c)
{
    E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;
    E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;
}
bool bfs(int S,int T)
{
    static int Q[MAXN]; memset(dis,-1,sizeof(dis[0])*N);
    dis[S]=0; Q[0]=S;
    for (int h=0,t=1,u,v,it;h<t;++h)
    {
        for (u=Q[h],it=G[u];~it;it=E[it].nx)
        {
            if (dis[v=E[it].v]==-1&&E[it].c>E[it].f)
            {
                dis[v]=dis[u]+1; Q[t++]=v;
            }
        }
    }
    return dis[T]!=-1;
}
int dfs(int u,int T,int low)
{
    if (u==T) return low;
    int ret=0,tmp,v;
    for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
    {
        if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f)
        {
            if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
            {
                ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp;
            }
        }
    }
    if (!ret) dis[u]=-1; return ret;
}
int dinic(int S,int T)
{
    int maxflow=0,tmp;
    while (bfs(S,T))
    {
        memcpy(cur,G,sizeof(G[0])*N);
        while (tmp=dfs(S,T,inf)) maxflow+=tmp;
    }
    return maxflow;
}
int n,m;
pair<int,int> p[2050];
bool check(int x)
{
    int s=0,t=4002;
    init(4005);
    for(int i=1;i<=m;i++)
    {
        link(s,i+n,1);
        link(i+n,p[i].first,1);
        link(i+n,p[i].second,1);
    }
    for(int i=1;i<=n;i++)
        link(i,t,x);
    return dinic(s,t)==m;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d%d",&p[i].first,&p[i].second);
        int l=0,r=m,ans=0;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))r=mid-1,ans=mid;
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
}