Chenfan Blog

Do cool things that matter.

0%

HDU 4009 Transfer water 最小树形图

Posted on Edited on In

Transfer water

Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)

Problem Description

XiaoA lives in a village. Last year flood rained the village. So they decide to move the whole village to the mountain nearby this year. There is no spring in the mountain, so each household could only dig a well or build a water line from other household. If the household decide to dig a well, the money for the well is the height of their house multiplies X dollar per meter.

If the household decide to build a water line from other household, and if the height of which supply water is not lower than the one which get water, the money of one water line is the Manhattan distance of the two households multiplies Y dollar per meter. Or if the height of which supply water is lower than the one which get water, a water pump is needed except the water line. Z dollar should be paid for one water pump. In addition,therelation of the households must be considered. Some households may do not allow some other households build a water line from there house. Now given the 3‐dimensional position (a, b, c) of every household the c of which means height, can you calculate the minimal money the whole village need so that every household has water, or tell the leader if it can’t be done.

Input

Multiple cases. First line of each case contains 4 integers n (1<=n<=1000), the number of the households, X (1<=X<=1000), Y (1<=Y<=1000), Z (1<=Z<=1000). Each of the next n lines contains 3 integers a, b, c means the position of the i‐th households, none of them will exceeded 1000. Then next n lines describe the relation between the households. The n+i+1‐th line describes the relation of the i‐th household. The line will begin with an integer k, and the next k integers are the household numbers that can build a water line from the i‐th household. If n=X=Y=Z=0, the input ends, and no output for that.

Output

One integer in one line for each case, the minimal money the whole village need so that every household has water. If the plan does not exist, print “poor XiaoA” in one line.

Sample Input

2 10 20 30
1 3 2
2 4 1
1 2
2 1 2
0 0 0 0

Sample Output

30

题意

有一个村庄需要修建供水系统。每户居民的房子都有一个三维坐标，每户居民可以选择自己挖井或者从其他居民家里引水。挖水井和引水分别需要花费不同的钱。每户居民有一个意愿表，只愿意对表内的居民家供水。最后要求计算出能为所有居民供水的最小花费。

分析

本题具有明显的方向性，如果把供水用一条有向边表示的话，很明显能够发现本题抽象到最后是一个最小树形图。

因此思路就明确了，求解最小树形图可以直接套模板，需要做的就是根据题目条件来建图。

这里没有指定水源从哪来，但是至少是需要有1户人家挖水井才能有水。因此首先用0表示虚节点，从虚节点向所有人家连有向边，边长即为每户人家挖水井需要的花费，然后根据每户人家的意愿表加入有向边，处理一下边权。

最后套一个模板求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU 4009
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
const int M = N*N;
typedef struct nod
{
    int a,b,c;
} node;
node edge[M];
int predge[N],id[N],visit[N],in[N];
int dmst(int root,int n,int m)//n表示点数，m表示边数，root表示根
{
    int u,v;
    int ret=0;
    while(true)
    {
        for(int i=0;i<n;i++) in[i]=INT_MAX;
        for(int i=0;i<m;i++)
        {
            if(edge[i].c<in[edge[i].b]&&edge[i].a!=edge[i].b)
            {
                predge[edge[i].b]=edge[i].a;//找出每个点的最小入弧
                in[edge[i].b]=edge[i].c;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(i==root) continue;
            if(in[i]==INT_MAX) return -1;
        }
        in[root]=0;
        int cnt=0;
        memset(id,-1,sizeof(id));
        memset(visit,-1,sizeof(visit));
        for(int i=0;i<n;i++)
        {
            ret+=in[i];//进行缩圈
            v=i;
            while(visit[v]!=i&&id[v]==-1&&v!=root)
            {
                visit[v]=i;
                v=predge[v];
            }
            if(v!=root&&id[v]==-1)
            {
                for(u=predge[v];u!=v;u=predge[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++)
        {
            v=edge[i].b;//进行缩点，重新标记。
            edge[i].a=id[edge[i].a];
            edge[i].b=id[edge[i].b];
            if (edge[i].a!=edge[i].b) edge[i].c-=in[v];
        }
        n=cnt;
        root=id[root];
    }
    return ret;
}

typedef struct hnod
{
    int x,y,z;
} hnode;
hnode house[N];

int dis(int x,int y)
{
    return abs(house[x].x-house[y].x)+abs(house[x].y-house[y].y)+abs(house[x].z-house[y].z);
}

int main()
{
    int n,x,y,z;
    scanf("%d%d%d%d",&n,&x,&y,&z);
    while (n||x||y||z)
    {
        for (int i=1;i<=n;i++)
        scanf("%d%d%d",&house[i].x,&house[i].y,&house[i].z);
        int tot=0;
        for (int i=1;i<=n;i++)
        {
            int p;
            scanf("%d",&p);
            for (int j=1;j<=p;j++)
            {
                int d;
                scanf("%d",&d);
                edge[tot].a=i;
                edge[tot].b=d;
                edge[tot].c=dis(i,d)*y;
                if (house[i].z<house[d].z) edge[tot].c+=z;
                tot++;
            }
        }
        for (int i=1;i<=n;i++)
        {
            edge[tot].a=0;
            edge[tot].b=i;
            edge[tot].c=house[i].z*x;
            tot++;
        }

        printf("%d\n",dmst(0,n+1,tot));
        
        scanf("%d%d%d%d",&n,&x,&y,&z);
    }

    return 0;
}
Related Posts