热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

hdu4009Transferwater有固定根的最小树形图

ProblemDescriptionXiaoAlivesinavillage.Lastyearfloodrainedthevillage

Problem Description
XiaoA lives in a village. Last year flood rained the village. So they decide to move the whole village to the mountain nearby this year. There is no spring in the mountain, so each household could only dig a well or build a water line from other household. If the household decide to dig a well, the money for the well is the height of their house multiplies X dollar per meter. If the household decide to build a water line from other household, and if the height of which supply water is not lower than the one which get water, the money of one water line is the Manhattan distance of the two households multiplies Y dollar per meter. Or if the height of which supply water is lower than the one which get water, a water pump is needed except the water line. Z dollar should be paid for one water pump. In addition,therelation of the households must be considered. Some households may do not allow some other households build a water line from there house. Now given the 3‐dimensional position (a, b, c) of every household the c of which means height, can you calculate the minimal money the whole village need so that every household has water, or tell the leader if it can’t be done.
 

Input
Multiple cases. 
First line of each case contains 4 integers n (1<=n<=1000), the number of the households, X (1<=X<=1000), Y (1<=Y<=1000), Z (1<=Z<=1000). 
Each of the next n lines contains 3 integers a, b, c means the position of the i‐th households, none of them will exceeded 1000. 
Then next n lines describe the relation between the households. The n+i+1‐th line describes the relation of the i‐th household. The line will begin with an integer k, and the next k integers are the household numbers that can build a water line from the i‐th household. 
If n=X=Y=Z=0, the input ends, and no output for that. 
 

Output
One integer in one line for each case, the minimal money the whole village need so that every household has water. If the plan does not exist, print “poor XiaoA” in one line. 
 

Sample Input
 
  
2 10 20 30 1 3 2 2 4 1 1 2 2 1 2 0 0 0 0
 

Sample Output
 
  
30
Hint
In 3‐dimensional space Manhattan distance of point A (x1, y1, z1) and B(x2, y2, z2) is |x2‐x1|+|y2‐y1|+|z2‐z1|.

//


#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1501;
const int TOOBIG = (1<<30);
//1是固定根
/*
 if(!min_shuxingtu()) puts("impossible");
else{
    printf("%.0lf\n",ans);
}
*/
//不能将!=-1改成>0,==-1改成<0
double g[maxn][maxn], mincost[maxn];
int pre[maxn], n;
bool vis[maxn], exist[maxn];
double  ans;


void combine(int *list, int h, int r) {
    // 环中的点依序保存在 list[h..r] 中,将这个环缩成一个点
    memset(vis, 0, sizeof(vis));
    for (int i = h; i <= r; i++) {
        vis[list[i]] = true;
        exist[list[i]] = false;
    }
    int now = list[h];
    // 首先处理边权问题
    double newg[maxn];
    for (int j = 1; j <= n; j++) newg[j] = TOOBIG;
    for (int i = h; i <= r; i++) {
        int x = list[i];
        ans += mincost[x];
        for (int j = 1; j <= n; j++) if (!vis[j] && exist[j]) {
            if (g[j][x] != -1) {
                double tmp = g[j][x] - mincost[x];
                newg[j] = min(newg[j], tmp);
            }
            if ((g[x][j] != -1 && g[x][j]         }
    }
    exist[now] = true;
    for (int j = 1; j <= n; j++) g[j][now] = newg[j];
    // 然后处理缩成的点引出的最小边
    for (int i = 2; i <= n; i++) if (exist[i] && !vis[i] && vis[pre[i]]) pre[i] = now;
    // 最后处理缩成的点自己的最小边
    mincost[now] = TOOBIG;
    for (int i = 1; i <= n; i++)
        if (exist[i] && i != now && g[i][now] != -1 && g[i][now]             mincost[now] = g[i][now];
            pre[now] = i;
        }
}


bool find_circle(int *list, int &h, int &r) {
    // 由于每个点的 vis 只会被标记一次,所以这个过程是 O(n) 的
    // 如果找到了环那么将环中的点依序保存在 list[h..r] 中
    int mark[maxn];
    memset(vis, 0, sizeof(vis));
    for (int k = 2; k <= n; k++) if (!vis[k] && exist[k]) {
        memset(mark, 0, sizeof(mark));
        r = 0;
        int i = k;
        for (; i != 1 && !mark[i] && !vis[i]; i = pre[i]) {
            vis[i] = true;
            r++;
            list[r] = i;
            mark[i] = r;
        }
        if (mark[i]) {
            h = mark[i];
            return true;
        }
    }
    return false;
}


void dfs(int v){
    vis[v] = true;
    for (int i = 1; i <= n; i++) if (!vis[i] && g[v][i] != -1) dfs(i);
}


bool min_shuxingtu() {
    // 求以 1 为根的最小树形图,原图以邻接矩阵保存于 g[1..n][1..n] 中,求解将破坏 g 矩阵
    // 如果存在返回 true,并且将最小树形图的边权和放在 ans 中,否则返回 false
    memset(vis, 0, sizeof(vis));
    dfs(1);
    for (int i = 1; i <= n; i++) if (!vis[i]) return false;
    // 初始化 mincost 和 pre 和 id
    for (int i = 1; i <= n; i++) exist[i] = true;
    for (int i = 2; i <= n; i++) {
        mincost[i] = TOOBIG;
        for (int j = 1; j <= n; j++)
            if (j != i && g[j][i] != -1 && g[j][i]                 mincost[i] = g[j][i];
                pre[i] = j;
            }
    }
    ans = 0;
    int list[maxn], h, r;
    while (find_circle(list, h, r)) combine(list, h, r);
    for (int i = 2; i <= n; i++) if (exist[i]) ans += mincost[i];
    return true;
}


int ha[2000], hb[2000], hc[2000];
int x, y, z;


int abs(int x){ return (x <0 ? -x : x); }


int dist(int i, int j){
    int ret = abs(ha[i] - ha[j]) + abs(hb[i] - hb[j]) + abs(hc[i] - hc[j]);
    ret *= y;
    if (hc[i]     return ret;
}




int main() {
    while(scanf("%d%d%d%d",&n,&x,&y,&z)==4&&n) {
        n++;
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=-1;
        for (int i = 2; i <= n; i++) scanf("%d %d %d", &ha[i], &hb[i], &hc[i]);
        for (int i = 2; i <= n; i++) {
            g[1][i] = hc[i]*x;
            int k;
            scanf("%d", &k);
            while (k--) {
                int j;
                scanf("%d", &j);
                j++;
                if (j != i) {
                    int c = dist(i, j);
                    //if(g[i][j] == -1 || g[i][j] > c) g[i][j] = c;
                    g[i][j]=c;
                }
            }
        }
        if (!min_shuxingtu()) puts("Impossible");
        else printf("%.0lf\n",ans);
    }
    return 0;
}
//对于不固定根的最小树形图,新加一个点,和每个点连权相同的边,
//这个权大于原图所有边权的和,这样这个图固定跟的最小树形图和原图
//不固定跟的最小树形图就是对应的了。


推荐阅读
author-avatar
xinzhugedonny
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有