hdu4009最小树形图板子题

/*
调了一下午的最小树形图，昨天刚刚看懂模板。。
最小树形图，就是有向图的最小生成树，很神奇==
*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define MAXN 1002

#define INF 0x3f3f3f3f

using namespace std;

struct Node{

    int x,y,z;

}nodes[MAXN];

struct Edge{

    int u,v,w;

}e[MAXN*MAXN];

int tot;

int dist(int a,int b,int y,int z){

    int res=;

    res+=abs(nodes[a].x-nodes[b].x)*y+abs(nodes[a].y-nodes[b].y)*y+abs(nodes[a].z-nodes[b].z)*y;

    if(nodes[a].z<nodes[b].z)

        res+=z;

    return res;

}

int pre[MAXN],id[MAXN],visit[MAXN],in[MAXN];

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

    int res=,u,v;

    while(){

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

            in[i]=INF;

        //建立最小弧集E

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

            if(e[i].u!=e[i].v && e[i].w<in[e[i].v]){

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

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

            }

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

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

                return -;//不存在最小树形图

        int tn=;

        memset(id,-,sizeof id);

        memset(visit,-,sizeof visit);

        in[root]=;

        for(int i=;i<n;i++){//找环染色

            res+=in[i];

            v=i;

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

                visit[v]=i;

                v=pre[v];

            }//找环

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

                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;){//

            v=e[i].v;

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

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

            if(e[i].u!=e[i].v)//如果是在不同的环里

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

            else

                swap(e[i],e[--m]);

        }

        n=tn;//剩下tn个点

        root=id[root];

    }

    return res;

}

int main(){

    int n,x,y,z,k,v;

    while(scanf("%d%d%d%d",&n,&x,&y,&z)!=EOF && n){

        tot=;

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

            scanf("%d%d%d",&nodes[i].x,&nodes[i].y,&nodes[i].z);

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

            scanf("%d",&k);

            while(k--){

                scanf("%d",&v);

                e[tot].u=u;

                e[tot].v=v;

                e[tot].w=dist(u,v,y,z);

                tot++;

            }

        }

        int root=;

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

            e[tot].u=root;

            e[tot].v=i;

            e[tot].w=x*nodes[i].z;

            tot++;

        }

        printf("%I64d\n",zhuliu(root,n+,tot));

    }

    return ;

}