uva11183 最小树形图模板题

很简单的模板题，不多说了

#include<iostream>

#include<cstring>

#include<cstdio>

#define INF 0x3f3f3f3f

#define MAXN 1000

#define ll long long

using namespace std;

struct Edge{

    int u,v,cost;

}edge[MAXN*];

int pre[MAXN],id[MAXN],vis[MAXN];

ll in[MAXN];

ll zhuliu(int root,int n,int m){

    ll res=;

    while(){

        for(int i=;i<n;i++) in[i]=INF;

        for(int i=;i<m;i++)

            if(edge[i].u!=edge[i].v && edge[i].cost<in[edge[i].v]){

                pre[edge[i].v]=edge[i].u;

                in[edge[i].v]=edge[i].cost;

            }

        for(int i=;i<n;i++)

            if(i!=root && in[i]==INF) return -;

        int tn=;

        memset(id,-,sizeof id);

        memset(vis,-,sizeof vis);

        in[root]=;

        for(int i=;i<n;i++){

            res+=in[i];

            int v=i;

            while(v!=root && id[v]==- && vis[v]!=i){

                vis[v]=i;

                v=pre[v];

            }

            if(id[v]==- && v!=root){

                for(int u=pre[v];u!=v;u=pre[u])

                    id[u]=tn;

                id[v]=tn++;

            }

        }

        if(tn==) break;

        for(int i=;i<n;i++)

            if(id[i]==-) id[i]=tn++;

        for(int i=;i<m;i++){

            int v=edge[i].v;

            edge[i].u=id[edge[i].u];

            edge[i].v=id[edge[i].v];

            if(edge[i].u!=edge[i].v)

                edge[i].cost-=in[v];

        }

        n=tn;

        root=id[root];

    }

    return res;

}

int main(){

    int N,n,m;

    cin >> N;

    for(int tt=;tt<=N;tt++){

        scanf("%d%d",&n,&m);

        for(int i=;i<m;i++)

            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost);

        int root=;

        ll res=zhuliu(root,n,m);

        if(res==-)

            printf("Case #%d: Possums!\n",tt);

        else

            printf("Case #%d: %d\n",tt,res);

    }

    return ;

}