UVA-11183 Teen Girl Squad （最小树形图、朱刘算法模板）

题目大意：给一张无向图，求出最小树形图。

题目分析：套朱-刘算法模板就行了。。。

代码如下：

# include<iostream>

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define LL long long

# define REP(i,s,n) for(int i=s;i<n;++i)

# define CL(a,b) memset(a,b,sizeof(a))

# define CLL(a,b,n) fill(a,a+n,b)

const int N=1005;

const int INF=1<<30;

struct Edge

{

    int fr,to,w;

};

Edge e[N*40];

int vis[N],ID[N],pre[N],in[N],n,m;

int zhu_liu(int root,int nv,int ne)

{

    int res=0;

    while(1)

    {

        CLL(in,INF,nv);

        REP(i,0,ne) if(e[i].fr!=e[i].to&&in[e[i].to]>e[i].w){

            in[e[i].to]=e[i].w;

            pre[e[i].to]=e[i].fr;

        }

        in[root]=0;

        REP(i,0,nv) if(in[i]==INF) return -1;

        int nodeCnt=0;

        CL(ID,-1);

        CL(vis,-1);

        REP(i,0,nv){

            res+=in[i];

            int v=i;

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

                vis[v]=i;

                v=pre[v];

            }

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

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

                    ID[u]=nodeCnt;

                ID[v]=nodeCnt++;

            }

        }

        if(nodeCnt==0) break;

        REP(i,0,nv) if(ID[i]==-1) ID[i]=nodeCnt++;

        REP(i,0,ne){

            int v=e[i].to;

            e[i].fr=ID[e[i].fr];

            e[i].to=ID[e[i].to];

            if(e[i].fr!=e[i].to)

                e[i].w-=in[v];

        }

        nv=nodeCnt;

        root=ID[root];

    }

    return res;

}

int main()

{

    int T,cas=0;

    scanf("%d",&T);

    while(T--)

    {

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

        REP(i,0,m)

        {

            scanf("%d%d%d",&e[i].fr,&e[i].to,&e[i].w);

        }

        int ans=zhu_liu(0,n,m);

        printf("Case #%d: ",++cas);

        if(ans<0)

            printf("Possums!\n");

        else

            printf("%d\n",ans);

    }

    return 0;

}