题目大意：有N个点。每一个点都有对应的三维坐标(x,y,z)
如今要求每一个点都能获得水，或者水的方式有两种 1.自己挖井，费用为X * 海拔高度z 2.铺设管道引水。 a.假设海拔高度小于引水处。费用为两地曼哈顿距离*Y b.假设海拔高度大于饮水处。费用为两地曼哈顿距离*Y + Z解题思路：设置一个虚根。虚根引向全部的点，权值为挖井的费用，接着依照要求连边，求出最小树形图就可以
#include#include #define N 1010#define abs(a) ((a)>0?(a):(-(a)))struct Edge{ int u, v, c;}E[N*N];struct Point{ int x, y, z;}P[N];int n, x, y, z, tot;void AddEdge(int u, int v, int c) { E[tot].u = u; E[tot].v = v; E[tot++].c = c;}void init() { tot = 0; for (int i = 1; i <= n; i++) { scanf("%d%d%d", &P[i].x, &P[i].y, &P[i].z); AddEdge(0, i, P[i].z * x); } int k, t; for (int i = 1; i <= n; i++) { scanf("%d", &k); while (k--) { scanf("%d", &t); if (t == i) continue; if (P[i].z >= P[t].z) { int dis = abs(P[t].x - P[i].x) + abs(P[t].y - P[i].y) + abs(P[t].z - P[i].z); AddEdge(i, t, dis * y); } else { int dis = abs(P[t].x - P[i].x) + abs(P[t].y - P[i].y) + abs(P[t].z - P[i].z); AddEdge(i, t, dis * y + z); } } }}#define INF 0x3f3f3f3fint in[N], pre[N], vis[N], id[N];int Directed_MST(int root, int n) { int ans = 0, u, v, tmp; while (1) { for (int i = 0; i < n; i++) in[i] = INF; for (int i = 0; i < tot; i++) { u = E[i].u; v = E[i].v; if (u != v && E[i].c < in[v]) { in[v] = E[i].c; pre[v] = u; } } memset(vis, -1, sizeof(vis)); memset(id, -1, sizeof(id)); in[root] = 0; int subnode = 0; for (int i = 0; i < n; i++) { ans += in[i]; tmp = i; while (vis[tmp] != i && tmp != root && id[tmp] == -1) { vis[tmp] = i; tmp = pre[tmp]; } if (id[tmp] == -1 && tmp != root) { u = pre[tmp]; while (u != tmp) { id[u] = subnode; u = pre[u]; } id[tmp] = subnode++; } } if (subnode == 0) break; for (int i = 0; i < n; i++) if (!(~id[i])) id[i] = subnode++; for (int i = 0; i < tot; i++) { tmp = E[i].v; E[i].u = id[E[i].u]; E[i].v = id[E[i].v]; if (E[i].u != E[i].v) E[i].c -= in[tmp]; } n = subnode; root = id[root]; } return ans;}void solve() { n++; int ans = Directed_MST(0,n); if (ans == -1) printf("poor XiaoA\n"); else printf("%d\n", ans);}int main() { while (scanf("%d%d%d%d", &n, &x, &y, &z) != EOF && n + x + y + z) { init(); solve(); } return 0;}