本文共 3784 字，大约阅读时间需要 12 分钟。

题意：一个村庄有n个家，编号从1~n，每个家坐标为(a,b,c)，现需要引水，可自家挖井，也可建水管从别人家取水。若是自家挖井，消耗费用为c*X，假如是从别的家取水，费用为两家的曼哈顿距离*Y，假如供水人家的c小于取水人家的c，则需要添加水泵价格Z。每家都可以自己建造井，但并不是可以从任意人家取水，可从哪家取水已给出。

题解：朱刘算法+虚根

1.这道题依然需要自己定一个虚根，标号为0，视为水源，挖井人家可从0处取水。这个虚根不用去掉，因为题目中需要水源。

2.套用不定根最小树形图模板即可。

3.注意：因为标号与for循环判断条件的缘故，下一个while循环用的点数n为当前环数tn - 1。视具体情况决定下次使用的点数。

/* 最小树形图 朱刘算法模板 时间复杂度O(nm) 数据为int型 */  #include <cstdio>  #include <cstring> #include<math.h> #include <algorithm>  #define MAXN 2001  #define inf 1e9 using namespace std; struct Node{  int a , b , c ;	} node[MAXN] ;struct Edge  {      int from, to ;	int cost;  };  Edge edge[MAXN * MAXN];  int pre[MAXN];//存储父节点  int vis[MAXN];//标记作用  int id[MAXN];//id[i]记录节点i所在环的编号  int in[MAXN];//in[i]记录i入边中最小的权值  int x , y , z ;int zhuliu(int root, int n, int m)//root根 n点数 m边数  {      int res = 0 ;	int u , v ;      while(1)      {          for(int i = 0 ; i <= n ; i++)              in[i] = inf ;//初始化          for(int i = 0 ; i < m ; i++)          {              Edge E = edge[i];              if(E.from != E.to && E.cost < in[E.to])              {                  pre[E.to] = E.from;//记录前驱                  in[E.to] = E.cost;//更新              }          }          for(int i = 0 ; i <= n ; i++)              if(i != root && in[i] == inf)                  return -1;//有其他孤立点 则不存在最小树形图          //找有向环          int tn = 0 ;//记录当前查找中 环的总数          memset(id, -1, sizeof(id));          memset(vis, -1, sizeof(vis));          in[root] = 0;//根          for(int i = 0 ; i <= n; i++)          {              res += in[i];//累加              v = i;              //找图中的有向环 三种情况会终止while循环              //1,直到出现带有同样标记的点说明成环              //2,节点已经属于其他环              //3,遍历到根              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] = tn;//记录节点所属的 环编号                  id[v] = tn ++ ;//记录节点所属的 环编号  环编号累加              }          }          if(tn == 0) break;//不存在有向环          //可能存在独立点          for(int i = 0 ; i <= n ; i++)              if(id[i] == -1)                  id[i] = tn ++ ;//环数累加          //对有向环缩点  和SCC缩点很像吧          for(int i = 0; i < m ; i++)          {              v = edge[i].to;              edge[i].from = id[edge[i].from];              edge[i].to = id[edge[i].to];              //<u, v>有向边               //两点不在同一个环 u到v的距离为 边权cost - in[v]              if(edge[i].from != edge[i].to)                  edge[i].cost -= in[v] ;//更新边权值 继续下一条边的判定          }          //以环总数为下次操作的点数 继续执行上述操作 直到没有环          n = tn - 1 ;//注意需要tn-1         root = id[root];      }      return res;  }  int main()  {      int n , m ;//N个点 M条有向边      int i , j , k ;    int v ;    int ans ;	while(scanf("%d%d%d%d", &n , &x , &y , &z)  && !(n == 0 && x == 0 && y == 0 && z == 0))      {  	        for(i = 1 ; i <= n ; i ++)            scanf("%d%d%d" , &node[i].a , &node[i].b , &node[i].c) ;        m = 0 ;        for(i = 1 ; i <= n ; i ++)        {        	scanf("%d" , &k) ;        	for(j = 1 ; j <= k ; j ++)        	{        		scanf("%d" , &v) ;        		if(i == v)        		   continue ;        		edge[m].from = i ;        		edge[m].to = v ;        		edge[m].cost = y * (abs(node[i].a - node[v].a) + abs(node[i].b - node[v].b) + abs(node[i].c - node[v].c)) ;			    if(node[i].c < node[v].c)			       edge[m].cost += z ;		       				m ++ ;			}	    }       		for(i = 1 ; i <= n ; i ++)		{			edge[m].from = 0 ;        	edge[m].to = i ;        	edge[m].cost = x * node[i].c ;        	m ++ ;		}         		ans = zhuliu(0 , n , m) ;  			printf("%d\n" , ans) ;                }      return 0 ;  }