【题意】：有n个地方需要供水，每个地方都可以选择是自己挖井，还是从别的地方引水，根据方法不同和每个地方的坐标不同，花费也不同，现在给出每个地方的坐标，花费的计算方法，以及每个地方可以给哪些地方供水（即对方可以从这里引水），求给所有地方供水的最小花费。
【题解】：比赛的时候还没有学最小树形图，学了之后发现这题其实就是模板题，关键是要有一份好的模板。显然对于每个地方，只有一种供水方式就足够了，这样也能保证花费最小，而每个地方都可以自己挖井，所以是不可能出现无解的情况的，为了方便思考，我们引入一个虚拟点，把所有自己挖井的都连到这个点，边权为挖井的花费，而如果i能从j处引水，则从j向i连边，边权为引水的花费，然后对这个有向图，以虚拟点为根，求最小树形图即可（最小树形图即为有向图的最小生成树）。用邻接矩阵会TLE，用邻接表就可以ac了。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "cmath"
5 using namespace std;
6 #define maxn 1005
7 #define maxm 1005000
8 int n, m;
9 #define type int
10 const type inf = 1 << 30;
11 int pre[maxn],id[maxn],visit[maxn], tot;
12 type in[maxn];
13 int root;
14 struct house {
15 int x, y, z;
16 }h[maxn];
17 struct Edge {
18 int u,v;
19 type cost;
20 }et[maxm];
21
22 void init() {
23 tot = 0;
24 }
25
26 void addedge(int u, int v, type cost) {
27 Edge e = {u, v, cost};
28 et[tot++] = e;
29 }
30
31 type getdist(int a, int b) {
32 return abs(h[a].x - h[b].x) +abs(h[a].y - h[b].y) +abs(h[a].z - h[b].z);
33 }
34
35 type dirmst(int root,int nv,int ne) {//点数+1,边数+1
36 type ret = 0;
37 while(1)
38 {
39 //find the smallest in-arc
40 fill(&in[0], &in[maxn], inf);
41 for(int i = 0; i < ne;i++) {
42 int u = et[i].u, v = et[i].v;
43 if(et[i].cost < in[v] && u != v)
44 pre[v] = u, in[v] = et[i].cost;
45 }
46 //there are some nodes other than root with no in-arc connected to it
47 for(int i = 0;i < nv;i++)
48 if(in[i] == inf && i != root) return -1;
49 //find the dir circle
50 int cntnode = 0;
51 memset(id, -1, sizeof(id));
52 memset(visit, -1, sizeof(visit));
53 in[root] = 0;
54 for(int i = 0;i < nv;i++) {
55 ret += in[i];
56 int v = i;
57 while(visit[v] != i && id[v] == -1 && v != root)
58 visit[v] = i, v = pre[v];
59 if(v != root && id[v] == -1) {
60 for(int u = pre[v]; u != v; u = pre[u])
61 id[u] = cntnode;
62 id[v] = cntnode++;
63 }
64 }
65 if(cntnode == 0) break;//no circle
66 for(int i = 0;i < nv;i++)
67 if(id[i] == -1) id[i] = cntnode++;
68 //compress the nodes
69 for(int i = 0;i < ne;i++) {
70 int v = et[i].v;
71 et[i].u = id[et[i].u];
72 et[i].v = id[et[i].v];
73 if(et[i].u != et[i].v)
74 et[i].cost -= in[v];
75 }
76 nv = cntnode;
77 root = id[root];
78 }
79 return ret;
80 }
81 int a, b, c, k, v;
82 int main() {
83 while(~scanf("%d%d%d%d", &n, &a, &b, &c)) {
84 if(!n && !a && !b && !c) break;
85 init();
86 root = 0;
87 for(int i = 1; i <= n; i++) {
88 scanf("%d%d%d", &h[i].x, &h[i].y, &h[i].z);
89 addedge(root, i, h[i].z * a);
90 }
91 for(int i = 1; i <= n; i++) {
92 scanf("%d", &k);
93 for(int j = 0; j < k; j++) {
94 scanf("%d", &v);
95 if(v == i) continue;
96 type cost = getdist(v, i) * b;
97 if(h[i].z < h[v].z) cost += c;
98 addedge(i, v, cost);
99 }
100 }
101 type ans = dirmst(root, n + 1, tot);
102 printf("%d\n", ans);
103 }
104 return 0;
105 }