首页 > 代码库 > hdu 4009 Transfer water(最小树形图:有向图的最小生成树模板)
hdu 4009 Transfer water(最小树形图:有向图的最小生成树模板)
题目:
链接:点击打开链接
题意:
有n个村庄,要求使得每个村庄都能得到水的最小费用。每个村庄可以通过挖井或从其他村庄修水路获得水。挖井的费用是房子的高度乘以X,修水道的费用和有向图边的起点和终点的高度有关。
思路:
代码:
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; #define inf 0x3f3f3f3f const int maxm=1200000; const int maxn=1200; struct point { int x,y,z; } p[maxn]; struct edge { int u,v,w; } e[maxm]; int pre[maxn],id[maxn],vis[maxn],in[maxn]; int n,m; void add(int u,int v,int w) { e[m].u=u,e[m].v=v,e[m++].w=w; } int dist(point a,point b) { return abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z); } int directedMST(int root) { int res=0,nv=n,i; while (1) { for (i=0; i<nv; i++) { in[i]=inf; } for (i=0; i<m; i++) { int u=e[i].u; int v=e[i].v; if (e[i].w<in[v]&&u!=v) { pre[v]=u; in[v]=e[i].w; } } for (i=0; i<nv; i++) { if (i==root)continue; if (in[i]==inf)return -1; } int cntnode=0; memset(id,-1,sizeof(id)); memset(vis,-1,sizeof(vis)); in[root]=0; for (i=0; i<nv; 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]=cntnode; } id[v]=cntnode++; } } if (cntnode==0) break; for (i=0; i<nv; i++) { if (id[i]==-1)id[i]=cntnode++; } for (i=0; i<m; i++) { int v=e[i].v; e[i].u=id[e[i].u]; e[i].v=id[e[i].v]; if (e[i].u!=e[i].v) { e[i].w-=in[v]; } } nv=cntnode; root=id[root]; } return res; } int main(void) { //freopen("input.txt","r",stdin); int x,y,z; while(scanf("%d%d%d%d",&n,&x,&y,&z)==4 && (n+x+y+z)) { m=0; n++; for(int i=1; i<n; i++) { scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z); add(0,i,x*p[i].z); } for(int i=1; i<n; i++) { int k,t; scanf("%d",&k); while(k--) { scanf("%d",&t); if(t == i) continue; int cost = dist(p[i],p[t])*y; if(p[t].z > p[i].z) cost += z; add(i,t,cost); } } printf("%d\n",directedMST(0)); } return 0; }
-------------------------------------------------------
战斗,从不退缩;奋斗,永不停歇~~~~~~~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。