#include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<set> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 1100 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef int type; using namespace std; int n, X, Y, Z, m; struct point { int x, y, z; }p[maxn]; struct node { int u, v; type w; }e[maxn * maxn]; type dis(point a, point b) { return abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z); } int pre[maxn], id[maxn], vis[maxn]; type in[maxn]; type Directed_MST(int root, int NV, int NE) { type ret = 0; while(true) { for (int i = 0; i < NV; i++) in[i] = INF; for (int i = 0; i < NE; i++) { int u = e[i].u, v = e[i].v; if (e[i].w < in[v] && u != v) { pre[v] = u; in[v] = e[i].w; } } for (int i = 0; i < NV; i++) { if (i == root) continue; if (in[i] == INF) return -1; } int cntcode = 0; mem(id, -1), mem(vis, -1); in[root] = 0; for (int i = 0; i < NV; i++) { ret += in[i]; int v = i; while(vis[v] != i && id[v] == -1 && v != root) { vis[v] = i; v = pre[v]; } if (v != root && id[v] == -1) { for (int u = pre[v]; u != v; u = pre[u]) id[u] = cntcode; id[v] = cntcode++; } } if (!cntcode) break; for (int i = 0; i < NV; i++) if (id[i] == -1) id[i] = cntcode++; for (int i = 0; i < NE; i++) { int v = 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].w -= in[v]; } NV = cntcode; root = id[root]; } return ret; } int main () { while(scanf("%d%d%d%d", &n, &X, &Y, &Z) != EOF) { if (n + X + Y + Z == 0) break; m = 0; for (int i = 1; i <= n; i++) { scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z); e[m].u = 0, e[m].v = i, e[m++].w = p[i].z * X; } for (int i = 1; i <= n; i++) { int k, d; scanf("%d", &k); while(k--) { scanf("%d", &d); e[m].u = i, e[m].v = d, e[m].w = dis(p[i], p[d]) * Y; if (p[i].z < p[d].z) e[m].w += Z; m++; } } type ans = Directed_MST(0, n + 1, m); if (ans == -1) puts("poor XiaoA"); else printf("%d\n", ans); } return 0; }
[HDU 4009] Transfer water (最小树形图)
原文:http://blog.csdn.net/sio__five/article/details/19016011