文章目录
Transfer water
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4009
题目大意:
在一个小镇里面,有N户人家,每户人家的地址为(x,y,z)。现在要建立一个水循环系统,其中建立一个水井的费用与地址的高度成正比,即为X*z。而从一户有水井的人家接水到自己家的费用为:(|x2-x1| + |y2-y1| + |z2-z1|) * Y。当有水井的房子高度比其低时,需要加额外的Z元抽水费。
而且每户人家只允许自己的好友从自己家接水。现在问最小费用为多少
解题思路:
可以假想出一个房子0,并且只有0有水井。那么对于每户人家,如果要自己打水,那么相当于从0处接水。题目就变成了求有向图的最小树形图。
#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; }