首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 4009 Transfer water(最小树形图+虚根)

HDU 4009 Transfer water(最小树形图+虚根)

作者头像
Ch_Zaqdt
发布2019-01-11 13:10:46
4610
发布2019-01-11 13:10:46
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4009

       题意是在三维地图上有n个村庄,然后要给这n个村庄通水,可以有两个选择,一个是自己打井,花费为村庄的高度乘X,还有就是可以和其他村庄连管道,如果被连接的村庄比连接的村庄低或相等,花费就是曼哈顿距离*Y(曼哈顿距离就是题目下方的Hint),如果被连接的村庄比连接的村庄高(水往高处流),就需要花费Z来加一个水泵,刚开始所有村庄都没有井和管道。输入格式是n,X,Y,Z,然后n行输入第i个村庄的三维坐标,接下来的n行的第一个数k表示后面有k个村庄要被第i个村庄连接。

       思路就是加一个虚根,权值为当前村庄自己打井的花费,然后去跑朱刘算法就好了。这样很巧妙的实现了当一个村庄没有村庄和它相连的时候可以自己打井。


AC代码:

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 1010 * 1010;
struct Node{
  int x,y,z;
}p[MAXN];
struct Edge{
    int u, v, cost;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], in[MAXN];
int n,m,root,pos,num;
int X, Y, Z;

void add(int u,int v,int w){
  edge[num].u = u;
  edge[num].v = v;
  edge[num++].cost = w;
}

int dist(int x,int y,int z,int x1,int y1,int z1){
  return (abs(x - x1) + abs(y - y1) + abs(z - z1));
}

int solve()
{
    int res = 0;
    while (1){
        for(int i=0;i<n;i++) in[i] = INF;
        for(int i=0;i<num;++i){
    			int u = edge[i].u, v = edge[i].v;
    			if(edge[i].cost < in[v] && u != v){
    				pre[v] = u;
						in[v] = edge[i].cost;
            // if(u == root) pos = i;      // 标记最小根
    			}
    		}
        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];
            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] = tn;
                id[v] = tn++;
            }
        }
        if (tn == 0) break;
        for (int i = 0; i < n; i++){
            if(id[i] == -1) id[i] = tn++;
        }
        for (int i = 0; i < num; i++){
            int v = edge[i].v;
            edge[i].u = id[edge[i].u];
            edge[i].v = id[edge[i].v];
            if (edge[i].u != edge[i].v) edge[i].cost -= in[v];
        }
        n = tn;
        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;
    for(int i=1;i<=n;i++){
      scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
    }
    int k;
    num = 0;
    for(int i=1;i<=n;i++){
      scanf("%d",&k);
      for(int j=0;j<k;j++){
        int xx;
        scanf("%d",&xx);
        // if(xx == i)continue;
        if(p[i].z >= p[xx].z)
          add(i, xx, dist(p[i].x, p[i].y, p[i].z, p[xx].x, p[xx].y, p[xx].z) * Y);
        else
          add(i, xx, dist(p[i].x, p[i].y, p[i].z, p[xx].x, p[xx].y, p[xx].z) * Y + Z);
      }
    }
    for(int i=1;i<=n;i++){
      add(0, i, p[i].z * X);
    }
    root = 0;
    n++;
    int ans = solve();
    if(ans == -1) puts("poor XiaoA");
    else printf("%d\n", ans);
  }
  return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年01月09日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档