每一户人家水的来源有两种打井和从别家接水，每户人家都可能向外输送水。
打井和接水两种的付出代价都接边。设一个超级源点，每家每户打井的代价就是从该点(0)到该户人家（1~n）的边的权值。接水有两种可能，从高处接水，那么代价是哈密顿距离与Y的乘积（可以认为就是水管的费用）；从低处接水，还要加上付出水泵的钱(水管+水泵的费用)。这样就可以建图了。图论，会建图的话问题就解决一半了。
然后，用模版来解题。不过朱刘算法的模版时间复杂度的差异还是蛮大的。我的模版的建图是邻接矩阵，时间复杂度是O(N^3)。超时，过不了。在网上找了一份按前向星（边的起点、终点、权值）建图的模版。AC了。该算法的复杂度是O(M)。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int N = 1010, M=1010000,INF=0x3f3f3f3f;
6 int pre[N],id[N],in[N],vis[N];
7 int tot;//边数
8 struct node
9 {
10 int u,v,w;
11 }e[M];
12 void adde(int i,int j,int k)
13 {
14 e[tot].u=i;e[tot].v=j;e[tot++].w=k;
15 }
16 int zhuliu(int root ,int vn)
17 {
18 int ans=0;
19 int cnt;
20 while(1)
21 {
22 for(int i=0;i<vn;i++)
23 in[i]=INF,id[i]=-1,vis[i]=-1;
24 for(int i=0;i<tot;i++)
25 {
26 if(in[e[i].v]>e[i].w && e[i].u!=e[i].v)
27 {
28 pre[e[i].v]=e[i].u;
29 in[e[i].v]=e[i].w;
30 }
31 }
32 in[root]=0;
33 pre[root]=root;
34 for(int i=0;i<vn;i++)
35 {
36 ans+=in[i];
37 if(in[i]==INF)//这一步可以看出是否存在这样一棵树形图，因此可以略去DFS
38 return -1;
39 }
40 cnt=0;
41 for(int i=0;i<vn;i++)
42 {
43 if(vis[i]==-1)
44 {
45 int t=i;
46 while(vis[t]==-1)
47 {
48 vis[t]=i;
49 t=pre[t];
50 }
51 if(vis[t]!=i || t==root) continue;
52 for(int j=pre[t];j!=t;j=pre[j])
53 id[j]=cnt;
54 id[t]=cnt++;
55 }
56 }
57 if(cnt==0) break;
58 for(int i=0;i<vn;i++)
59 if(id[i]==-1)
60 id[i]=cnt++;
61 for(int i=0;i<tot;i++)
62 {
63 int u,v;
64 u=e[i].u;
65 v=e[i].v;
66 e[i].u=id[u];
67 e[i].v=id[v];
68 e[i].w-=in[v];
69 }
70 vn=cnt;
71 root=id[root];
72 }
73 return ans;
74 }
75
76 struct Node
77 {
78 int a,b,c;
79 }nd[N];
80 int main()
81 {
82 //freopen("test.txt","r",stdin);
83 int n,x,y,z,i,j,k,d;
84 while(scanf("%d%d%d%d",&n,&x,&y,&z)!=EOF)
85 {
86 if(!n) break;
87 tot=0;
88 for(i=1;i<=n;i++)
89 {
90 scanf("%d%d%d",&nd[i].a,&nd[i].b,&nd[i].c);
91 adde(0,i,nd[i].c*x);
92 }
93 for(i=1;i<=n;i++)
94 {
95 scanf("%d",&k);
96 while(k--)
97 {
98 scanf("%d",&j);
99 if(i==j) continue;
100 d=abs(nd[i].a-nd[j].a)+abs(nd[i].b-nd[j].b)+abs(nd[i].c-nd[j].c);
101 d*=y;
102 if(nd[i].c<nd[j].c) d+=z;
103 adde(i,j,d);
104 }
105 }
106 int ans=zhuliu(0,n+1);
107 if(ans==-1) printf("poor XiaoA\n");
108 else printf("%d\n",ans);
109 }
110 return 0;
111 }
下面是邻接矩阵建图的模版，虽然超时了。但是模版还是有借鉴意义的。模版来自哈工大出版的《图论及应用》。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int N = 1010, INF=0x3f3f3f3f;
6 int Map[N][N];
7 bool vis[N],f[N];
8 //f是缩点标记,1表示该点已经被缩掉
9 int pre[N];
10 int zhuliu(int n)
11 {
12 int sum=0;
13 int i,j,k;
14 for(i=0;i<n;i++)
15 {
16 f[i]=0;
17 Map[i][i]=INF;
18 }
19 pre[0]=0;
20 while(1)
21 {
22 //求最短弧集合E0
23 for(i=1;i<n;i++)
24 {
25 if(f[i]) continue;
26 pre[i]=i;
27 for(j=0;j<n;j++)
28 if(!f[j]&&Map[j][i]<Map[pre[i]][i]) pre[i]=j;
29 if(pre[i]==i) return -1; //没有入边，不存在最小树形图
30 }
31 //检查E0
32 for(i=1;i<n;i++)
33 {
34 if(f[i]) continue ;
35 //从当前点开始找环
36 for(j=0;j<n;j++) vis[j]=0;
37 vis[0]=1;
38 j=i;
39 do
40 {
41 vis[j]=1;
42 j=pre[j];
43 }
44 while(!vis[j]) ;
45 if(!j) continue; //没有找到环
46 //收缩G中的有向环
47 i=j;
48 //将整个环的权值保存，累计入原图的最小树形图
49 do
50 {
51 sum+=Map[pre[j]][j];
52 j=pre[j];
53 }
54 while(j!=i) ;
55 j=i;
56 //对与环上的点有关的边，修改边权
57 do
58 {
59 for(k=0; k<n; k++)
60 if(!f[k]&&Map[k][j]<INF&&k!=pre[j])
61 Map[k][j]-= Map[pre[j]][j];
62 j=pre[j];
63 }
64 while(j!=i) ;
65 //缩点，将整个环缩成i号点，所有与环上的点有关的边转移到点i
66 for(j=0;j<n;j++)
67 {
68 if(j==i) continue;
69 for(k=pre[i]; k!=i; k=pre[k])
70 {
71 if(Map[k][j]<Map[i][j]) Map[i][j] =Map[k][j];
72 if(Map[j][k]<Map[j][i]) Map[j][i] =Map[j][k];
73 }
74 }
75 //标记环上其他的点为被缩掉
76 for(j=pre[i];j!=i;j=pre[j]) f[j] =1;
77 //当前环缩点结束，形成新的图G’，跳出继续求G’的最小树形图
78 break;
79 }
80 //如果所有的点都被检查且没有环存在，现在的最短弧集合E0就是
81 //最小树形图，累计如sum, 算法结束
82 if(i==n)
83 {
84 for(i=1;i<n;i++) if(!f[i]) sum+=Map[pre[i]][i];
85 break;
86 }
87 }
88 return sum;
89 }
90
91 struct node
92 {
93 int a,b,c;
94 }nd[N];
95 int main()
96 {
97 //freopen("test.txt","r",stdin);
98 int n,x,y,z,i,j,k,d;
99 while(scanf("%d%d%d%d",&n,&x,&y,&z)!=EOF)
100 {
101 if(!n) break;
102 for(i=0;i<=n;i++)
103 for(j=0;j<i;j++)
104 Map[j][i]=Map[i][j]=INF;
105 for(i=1;i<=n;i++)
106 {
107 scanf("%d%d%d",&nd[i].a,&nd[i].b,&nd[i].c);
108 Map[0][i]=nd[i].c*x;
109 }
110 for(i=1;i<=n;i++)
111 {
112 scanf("%d",&k);
113 while(k--)
114 {
115 scanf("%d",&j);
116 if(i==j) continue;
117 d=abs(nd[i].a-nd[j].a)+abs(nd[i].b-nd[j].b)+abs(nd[i].c-nd[j].c);
118 d*=y;
119 if(nd[i].c>=nd[j].c) d+=z;
120 Map[i][j]=min(d,Map[i][j]);
121 }
122 }
123 printf("%d\n",zhuliu(n+1));
124 }
125 return 0;
126 }