Hdu 4009 Transfer water（最小树形图）

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4009

思路：最小树形图：有向图的生成子图，满足图中有一个点无入弧，其他每个点只有一条入弧的情况下，权值最小。设立超级源点0，向每个点连边，权值为高度*X（即为挖井的费用）。可建设输水管道的两个点连边，注意判断高度差。以0作为根求最小树形图即可。朱刘算法，时间复杂度（V*E）。

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e3+50;
const int INF=0x3f3f3f3f;
struct Node
{
    int u,v,w;
    Node(int u=0,int v=0,int w=0):u(u),v(v),w(w) {}
} ;
struct Point
{
    int x,y,z;
};
int n,m,rt,X,Y,Z;
Point p[maxn];
vector<Node> g;
int vis[maxn],in[maxn];
int pre[maxn],ID[maxn];
int Directed_MST(int root,int n,int m)
{
    int ret=0;
    for(;;)
    {
        for(int i=0; i<n; i++) in[i]=INF;
        for(int i=0; i<m; i++)
        {
            int u=g[i].u,v=g[i].v;
            if(u!=v&&g[i].w<in[v])
            {
                pre[v]=u;
                in[v]=g[i].w;
            }
        }
        for(int i=0; i<n; i++)
        {
            if(i==root) continue;
            if(in[i]==INF) return -1;
        }
        int cnt=0;
        memset(ID,-1,sizeof(ID));
        memset(vis,-1,sizeof(vis));
        in[root]=0;
        for(int i=0; i<n; i++)
        {
            int v=i;
            ret+=in[i];
            while(v!=root&&ID[v]==-1&&vis[v]!=i)
            {
                vis[v]=i;
                v=pre[v];
            }
            if(v!=root&&ID[v]==-1)
            {
                for(int u=pre[v]; u!=v; u=pre[u]) ID[u]=cnt;
                ID[v]=cnt++;
            }
        }
        if(cnt==0) break;
        for(int i=0; i<n; i++)
            if(ID[i]==-1) ID[i]=cnt++;
        for(int i=0; i<m; i++)
        {
            int u=g[i].u,v=g[i].v;
            g[i].u=ID[u],g[i].v=ID[v];
            if(u!=v) g[i].w-=in[v];
        }
        n=cnt;
        root=ID[root];
    }
    return ret;
}
int dist(int i,int j)
{
    return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)+abs(p[i].z-p[j].z);
}
void prepare()
{
    g.clear();
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
        g.push_back(Node(0,i,p[i].z*X));
    }
    for(int i=1; i<=n; i++)
    {
        int k;
        scanf("%d",&k);
        for(int j=1; j<=k; j++)
        {
            int x;
            scanf("%d",&x);
            if(p[i].z<p[x].z) g.push_back(Node(i,x,Z+Y*dist(i,x)));
            else g.push_back(Node(i,x,Y*dist(i,x)));
        }
    }
}
int main()
{
    while(scanf("%d%d%d%d",&n,&X,&Y,&Z)!=EOF&&n)
    {
        prepare();
        int ret=Directed_MST(0,n+1,g.size());
        printf("%d\n",ret);
    }
    return 0;
}