题目链接：
HDU 4009 Transfer water
题意：
需要给n户人家通水。给出每户人家的三维坐标，每户人家自建一口井的花费是X,对于每户人家给出k[i]条边，to[j]，表示可以从第u=i户人家铺设一条水管道到第v=to[j]户人家，铺设的费用是两户人家三维坐标之差的绝对值之和*Y,如果u的高度小于v的高度还需要额外加上Z花费。问将n户人家都通上水的最小花费是多少？如果不能使每户人家都通上水就输出-1.
分析：
实际上不会输出-1的，因为每户人家都可以自建一口井。。。
每户人家之间的建边就按照题目叙述的那样建立边权就好了，主要是每户人家可以自建一口井花费X如何用边和边权表示？
可以新设一个根节点为0，从0到每户人家建立一条权值为X的边表示自建水井，这样子跑一下最小树形图就好了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 2010;
const int MAX_M = 1001000;
const int INF = 0x7fffffff;int n, X, Y, Z, K, NV, NE;
int vis[MAX_N], pre[MAX_N], ID[MAX_N];
ll In[MAX_N];struct Edge{int u, v;ll w;Edge() {}Edge(int _u, int _v, ll _w) : u(_u), v(_v), w(_w) { }
}edge[MAX_M];struct Point{int x, y, z;Point() {}Point(int _x, int _y, int _z) :x(_x), y(_y), z(_z) {}int dis(const Point& rhs) const {return abs(x - rhs.x) + abs(y - rhs.y) + abs(z - rhs.z);}
}point[MAX_N];ll ZLEdmonds(int root, int NV, int NE)
{ll res = 0, w;int u, v;while(1){for(int i = 0; i < NV; i++){In[i] = INF;}for(int i = 0; i < NE; i++){u = edge[i].u, v = edge[i].v, w = edge[i].w;if(u != v && w < In[v]){In[v] = w;pre[v] = u;}}for(int i = 0; i < NV; i++){if(i != root && In[i] == INF) return -1;}int cnt = 0;memset(vis, -1, sizeof(vis));memset(ID, -1, sizeof(ID));In[root] = 0;for(int i = 0; i < NV; i++){res += In[i];v = i;while(v != root && ID[v] == -1 && vis[v] != i){vis[v] = i;v = pre[v];}if(v != root && ID[v] == -1){for(u = pre[v]; u != v; u = pre[u]){ID[u] = cnt;}ID[v] = cnt ++;}}if(cnt == 0) break;for(int i = 0; i < NV; i++){if(ID[i] == -1) ID[i] = cnt++;}for(int i = 0; i < NE; i++){v = edge[i].v, u = edge[i].u;edge[i].u = ID[u], edge[i].v = ID[v];if(edge[i].u != edge[i].v){edge[i].w -= In[v];}}NV = cnt;root = ID[root];}return res;
}int main()
{IOS;while(~scanf("%d%d%d%d", &n, &X, &Y,&Z) && (n || X || Y || Z)){NE = 0;for(int i = 1; i <= n; i++){scanf("%d%d%d", &point[i].x, &point[i].y, &point[i].z);}for(int i = 1; i <= n; i++){scanf("%d", &K);int u = i;for(int j = 0; j < K; j++){int v;scanf("%d", &v);if(u == v) continue;ll w = point[u].dis(point[v]) * Y;if(point[u].z < point[v].z) w += Z;edge[NE++] = Edge(u, v, w);}}int root = 0;for(int i = 1; i <= n; i++){edge[NE++] = Edge(root, i, point[i].z * X);}NV = n + 1;ll ans = ZLEdmonds(root, NV, NE);if(ans == -1) printf("poor XiaoA\n");else printf("%lld\n", ans);}return 0;
}