kuangbin专题八 HDU4009 Transfer water （无定根最小树形图）

本文主要是介绍kuangbin专题八 HDU4009 Transfer water （无定根最小树形图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
在山上有N户人家，每家的坐标为(xi, yi, zi)。每户人家要吃水，要么自己打井，花费为X*zi，要么从别人的家引水渠代价为两家的曼哈顿距离*Y，如果这家的海拔比供水的低，还要另外再买一个价值为C的水泵。然后有N个k,表示的是每户人家可以引水渠到哪一家，现在问每家都有水喝的最低花费是多少。
题解：
一开始我纠结于如何在最小树形图中判断水泵到底安不安装，后来别人说直接把水泵的价格放进去单边权值就可以了，还有一点就是因为是不定根，所以我们要弄个超级源点，超级源点到各个点的权值为各个点打井的权值，然后就可以了，那个“poor XiaoA”其实是不会出现的。。因为最坏的情况，每家都可以自己打水井。
题外话：
有时候自己傻逼起来是真的可怕。。。把MAXN*MAXN放到点的结构体那里了，导致一直超时，对着模板都还能打错。。。妈的还有就是括号多了也看不清楚。。哎

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN=1000+7;
struct node1
{int u,v,w;
}map[MAXN*MAXN];
struct point
{int x,y,z;
}p[MAXN];
int pre[MAXN];
int ID[MAXN];
int IN[MAXN];
int vis[MAXN];
int n,m,X,Y,Z;
int zhuliu_mst(int root,int V,int E)
{int res=0;while(true){for(int i=0;i<V;i++) IN[i]=INF;for(int i=0;i<E;i++){int u=map[i].u;int v=map[i].v;if(map[i].w<IN[v]&&u!=v){pre[v]=u;IN[v]=map[i].w;}}for(int i=0;i<V;i++)//实际上这个判断每个点没入边是没必要的，因为可以自家打井 if(i!=root&&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<V;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;for(int i=0;i<V;i++){if(ID[i]==-1)ID[i]=cnt++;}for(int i=0;i<E;i++){int u=map[i].u;int v=map[i].v;map[i].u=ID[u];map[i].v=ID[v];if(ID[u]!=ID[v])map[i].w-=IN[v];}V=cnt;root=ID[root];}return res;
}
int main()
{while(~scanf("%d%d%d%d",&n,&X,&Y,&Z)){if(n==0&&X==0&&Y==0&&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);for(int i=1;i<=n;i++){int k,v;scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d",&v);map[m].u=i;map[m].v=v;map[m].w=(abs(p[i].x-p[v].x)+abs(p[i].y-p[v].y)+abs(p[i].z-p[v].z))*Y;if(p[i].z<p[v].z)map[m].w+=Z;m++;}}   for(int i=1;i<=n;i++){map[m].u=0;map[m].v=i;map[m].w=p[i].z*X;m++;}int ans=zhuliu_mst(0,n+1,m);//如果从点是1算的话，还是用n+1吧。。不然每次算完缩点之后的个数都要-1，麻烦 if(ans==-1)printf("poor XiaoA\n");//这句话不会出现的。。因为可以自家打井，但是还是写上去吧 elseprintf("%d\n",ans);}
}