最小树形图

struct node
{
    int now,nex,dis;
    node(int now,int nex,int dis):
        now(now),nex(nex),dis(dis) {}
    node(){}
} edge[40005];

int in[1005],id[1005],pre[1005],color[1005];

int mintreegraph(int n,int m,int root)
{
    int ans=0;
    while(1)
    {
        for(int i=1; i<=n; i++)
            in[i]=inf;
        for(int i=1; i<=m; i++)
        {
            int now=edge[i].now,nex=edge[i].nex;
            if(now!=nex && edge[i].dis<in[nex])
                pre[nex]=now,in[nex]=edge[i].dis;
        }
        in[root]=0;
        for(int i=1; i<=n; i++)
            if(in[i]==inf)return -1;
        int cont=0;
        memset(color,0,sizeof(color));
        memset(id,0,sizeof(id));
        for(int i=1; i<=n; i++)
        {
            ans+=in[i];
            int x=i;
            while(color[x]!=i && !id[x] && x!=root)
                color[x]=i,x=pre[x];
            if(!id[x] && x!=root)
            {
                cont++;
                while(!id[x])id[x]=cont,x=pre[x];
            }
        }
        if(!cont)return ans;
        for(int i=1; i<=n; i++)
            if(!id[i])id[i]=++cont;
        for(int i=1; i<=m; i++)
        {
            int now=edge[i].now,nex=edge[i].nex;
            edge[i].now=id[now],edge[i].nex=id[nex];
            if(now!=nex)edge[i].dis-=in[nex];
        }
        n=cont,root=id[root];
    }
}