首页 > 代码库 > HDU 4009 Transfer water 最小树形图

HDU 4009 Transfer water 最小树形图

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 301 3 22 4 11 22 1 20 0 0 0

【Sample Output】

30

【题意】

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

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

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

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

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

  1 /* ***********************************************  2 MYID    : Chen Fan  3 LANG    : G++  4 PROG    : HDU 4009  5 ************************************************ */  6   7 #include <iostream>  8 #include <cstdio>  9 #include <cstring> 10 #include <algorithm> 11  12 using namespace std; 13  14 const int N = 1010; 15 const int M = N*N; 16 typedef struct nod 17 { 18     int a,b,c; 19 } node; 20 node edge[M]; 21 int predge[N],id[N],visit[N],in[N]; 22 int dmst(int root,int n,int m)//n表示点数,m表示边数,root表示根 23 { 24     int u,v; 25     int ret=0; 26     while(true) 27     { 28         for(int i=0;i<n;i++) in[i]=INT_MAX; 29         for(int i=0;i<m;i++) 30         { 31             if(edge[i].c<in[edge[i].b]&&edge[i].a!=edge[i].b) 32             { 33                 predge[edge[i].b]=edge[i].a;//找出每个点的最小入弧 34                 in[edge[i].b]=edge[i].c; 35             } 36         } 37         for(int i=0;i<n;i++) 38         { 39             if(i==root) continue; 40             if(in[i]==INT_MAX) return -1; 41         } 42         in[root]=0; 43         int cnt=0; 44         memset(id,-1,sizeof(id)); 45         memset(visit,-1,sizeof(visit)); 46         for(int i=0;i<n;i++) 47         { 48             ret+=in[i];//进行缩圈 49             v=i; 50             while(visit[v]!=i&&id[v]==-1&&v!=root) 51             { 52                 visit[v]=i; 53                 v=predge[v]; 54             } 55             if(v!=root&&id[v]==-1) 56             { 57                 for(u=predge[v];u!=v;u=predge[u]) 58                     id[u]=cnt; 59                 id[v]=cnt++; 60             } 61         } 62         if (cnt==0) break; 63         for (int i=0;i<n;i++) 64         if (id[i]==-1) id[i]=cnt++; 65         for (int i=0;i<m;i++) 66         { 67             v=edge[i].b;//进行缩点,重新标记。 68             edge[i].a=id[edge[i].a]; 69             edge[i].b=id[edge[i].b]; 70             if (edge[i].a!=edge[i].b) edge[i].c-=in[v]; 71         } 72         n=cnt; 73         root=id[root]; 74     } 75     return ret; 76 } 77  78 typedef struct hnod 79 { 80     int x,y,z; 81 } hnode; 82 hnode house[N]; 83  84 int dis(int x,int y) 85 { 86     return abs(house[x].x-house[y].x)+abs(house[x].y-house[y].y)+abs(house[x].z-house[y].z); 87 } 88  89 int main() 90 { 91     int n,x,y,z; 92     scanf("%d%d%d%d",&n,&x,&y,&z); 93     while (n||x||y||z) 94     { 95         for (int i=1;i<=n;i++) 96         scanf("%d%d%d",&house[i].x,&house[i].y,&house[i].z); 97         int tot=0; 98         for (int i=1;i<=n;i++) 99         {100             int p;101             scanf("%d",&p);102             for (int j=1;j<=p;j++)103             {104                 int d;105                 scanf("%d",&d);106                 edge[tot].a=i;107                 edge[tot].b=d;108                 edge[tot].c=dis(i,d)*y;109                 if (house[i].z<house[d].z) edge[tot].c+=z;110                 tot++;111             }112         }113         for (int i=1;i<=n;i++)114         {115             edge[tot].a=0;116             edge[tot].b=i;117             edge[tot].c=house[i].z*x;118             tot++;119         }120 121         printf("%d\n",dmst(0,n+1,tot));122         123         scanf("%d%d%d%d",&n,&x,&y,&z);124     }125 126     return 0;127 }
View Code

 

HDU 4009 Transfer water 最小树形图