HDU4009 Transfer water【最小树形图】【不定根】

30

The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest

题目大意：一个村庄被洪水摧毁了，整个村庄都要转移。但是山上没有泉水，每户家庭只能

在自家挖一个水井或是修一个水渠从别的家庭引水。如果要修井，则修井费用和房子所在海

拔高度有关，每米X元。如果从别人的家里引水，如果从高于自己家高度的人家里引水，费

用为每米Y元。如果从低于自己家高度的人家里引水，每条要多花费Z元。现在给你这个村庄

N个家庭房屋的坐标(a,b,c)和三种花费X,Y,Z。接着给你各家之间能单向修建引水沟渠的限制。

问：能使全村庄的人喝上水的总修建费用最低为多少。若不能，则输出"poor XiaoA"。

思路：其实就是给你一个有向图，求有向图的最小树形图是多少。但是根结点不确定。在这

里可以假设一个根结点，也就是虚根，让所有家庭都从虚根引水(其实就是每家都自己修井)，

所以问题肯定有解，最后就是朱刘算法(模板)直接求最小树形图。

朱刘算法参考我的另一篇博文：http://blog.csdn.net/lianai911/article/details/42242371

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = 1010;
const int MAXM = 1000010;

struct Node
{
    int from;
    int to;
    int w;
};
Node Edges[MAXM];

struct Node1
{
    int x;
    int y;
    int z;
};
Node1 Point[MAXN];

int Dist(Node1 a,Node1 b)
{
    return abs(a.x-b.x) + abs(a.y-b.y) + abs(a.z-b.z);
}

int pre[MAXN],vis[MAXN],flag[MAXN],In[MAXN],sum;

int ZhuLiu(int root,int N,int M)
{
    sum = 0;
    while(true)
    {
        for(int i = 0; i < N; ++i)
            In[i] = INT_MAX;
        for(int i = 0; i < M; ++i)
        {
            int u = Edges[i].from;
            int v = Edges[i].to;
            if(Edges[i].w < In[v] && u != v)
            {
                pre[v] = u;
                In[v] = Edges[i].w;
            }
        }

        for(int i = 0; i < N; ++i)
        {
            if(i == root)
                continue;
            if(In[i] == INT_MAX)
                return -1;
        }
        int CntNode = 0;
        memset(flag,-1,sizeof(flag));
        memset(vis,-1,sizeof(vis));
        In[root] = 0;
        for(int i = 0; i < N; ++i)
        {
            sum += In[i];
            int v = i;
            while(vis[v] != i && flag[v] == -1 && v != root)
            {
                vis[v] = i;
                v = pre[v];
            }
            if(v != root && flag[v] == -1)
            {
                for(int u = pre[v]; u != v; u = pre[u])
                    flag[u] = CntNode;
                flag[v] = CntNode++;
            }
        }
        if(CntNode == 0)
            break;
        for(int i = 0; i < N; ++i)
        {
            if(flag[i] == -1)
                flag[i] = CntNode++;
        }
        for(int i = 0; i < M; ++i)
        {
            int v = Edges[i].to;
            Edges[i].from = flag[Edges[i].from];
            Edges[i].to = flag[Edges[i].to];
            if(Edges[i].from != Edges[i].to)
                Edges[i].w -= In[v];
        }
        N = CntNode;
        root = flag[root];
    }
    return sum;
}

int main()
{
    int N,M,X,Y,Z,k,d;
    while(~scanf("%d%d%d%d",&N,&X,&Y,&Z) && (N||X||Y||Z))
    {
        for(int i = 0; i < N; ++i)
            scanf("%d%d%d",&Point[i].x,&Point[i].y,&Point[i].z);
        M = 0;
        for(int i = 0; i < N; ++i)
        {
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d",&d);
                d--;
                Edges[M].from = i;
                Edges[M].to = d;
                Edges[M].w = Dist(Point[i],Point[d])*Y;
                if(Point[d].z > Point[i].z)
                    Edges[M].w += Z;
                M++;
            }
        }
        for(int i = 0; i < N; ++i)
        {
            Edges[M].from = N;
            Edges[M].to = i;
            Edges[M++].w = Point[i].z*X;
        }
        printf("%d\n",ZhuLiu(N,N+1,M));
    }


    return 0;
}

HDU4009 Transfer water【最小树形图】【不定根】

原文：http://blog.csdn.net/lianai911/article/details/42247047