HDU 4009

• 给出3维的点,由每个点的信息建立一个有向图,然后求出最小树形图

---

1. 建图方法:先把每个点的信息存着.根据每个点指向的另一个点的高度来建边,

   p[i].z >= p[to].z,就不需要水泵
   p[i].z < p[to].z,加上一个水泵

   题目告诉可以挖井是什么意思?

   题目也没有给出有向图的原点,我们又需要建一个虚根作为原点.

   那么可以将所有井的底部都抽象成虚根,正好到所有点的距离就是打井的距离

• 虚根建好了就跑朱刘算法就行了

  #include <iostream>
  #include <algorithm>
  #include <math.h>
  #include <string.h>
  using namespace std;
  const int maxn = 1005;
  const int inf = 0x3f3f3f3f;
  struct point {
  	int  x, y , z;
  }p[maxn];
  struct node {
  	int u, v , w;
  }edge[maxn * maxn];
  int pre[maxn], id[maxn], vis[maxn], n, m;
  int in[maxn];
  int x, y, z, num;
  int getdis(point a, point b) {
  	return abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z);
  }
  
  void edgeadd(int u,int v,int w) {
  	edge[num].u = u;
  	edge[num].v = v;
  	edge[num++].w = w;
  }
  
  int mst(int root, int nn, int mm) {
  	int res = 0;
  	while (1) {
  		for (int i = 0; i < nn; i++) in[i] = inf; //每个点的最小入边初始化为inf
  		for (int i = 0; i < mm; i++) {
  			int u = edge[i].u, v = edge[i].v;
  			if (edge[i].w < in[v] && u != v) { //不是自环,初始化每个点的入边最小值,和上一个点
  				pre[v] = u;
  				in[v] = edge[i].w;
  			}
  		}
  		for (int i = 0; i < nn; i++) {
  			if (i == root) continue;
  			if (in[i] == inf) return -1; //如果有除去根节点的任何一点没有入边,那么构成不了最小生成树
  		}
  		int cnt = 0;
  		memset(id, -1, sizeof id); memset(vis, -1, sizeof vis);
  		in[root] = 0;
  		for (int i = 0; i < nn; i++) {//一直找每个点的前一个点,缩点、标记点来建立新图
  			res += 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] = cnt;
  				id[v] = cnt++;
  			}
  		}
  		if (cnt == 0) break;
  		//有的点没有新id,比如根节点
  		for (int i = 0; i < nn; i++) if (id[i] == -1) id[i] = cnt++;
  		for (int i = 0; i < mm; i++) {
  			int u = edge[i].u, v = edge[i].v;
  			edge[i].u = id[u];
  			edge[i].v = id[v];
  			if (id[u] != id[v]) edge[i].w -= in[v];
  		}
  		nn = cnt;
  		root = id[root];
  	}
  	return res;
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	while (scanf("%d%d%d%d", &n, &x,&y,&z) != EOF && (x&&y&&z&&n)) {
  		for (int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].x, &p[i].y,&p[i].z);
  		int k = 0; num = 0;
  		for (int i = 1; i <= n; i++) { //m条有向边
  			scanf("%d",&k);
  			for (int j = 1; j <= k; j++) {
  				int to; scanf("%d",&to);
  				if (p[i].z >= p[to].z)
  					edgeadd(i, to, getdis(p[i], p[to]) * y);
  				else
  					edgeadd(i, to, getdis(p[i], p[to]) * y + z);
  			}
  		}
  		for (int i = 1; i <= n; i++) edgeadd(0,i,p[i].z * x);
  		n++; //加入了虚根
  		int ans = mst(0, n, num);
  		if (ans == -1) printf("poor XiaoA\n");
  		else printf("%d\n", ans);
  	}
  	return 0;
  }