hdu 4009 Transfer water

本文从WordPress迁移而来, 查看全部WordPress迁移文章

最小树形图

题意：给出3个值X,Y,Z，有n个点，每个点有一个3维坐标，再给出一个点的水可以流向哪些点。水可以从一个点流向另一个点，单向的；也可以在这个点内挖井也不需要通过其它点流过来。要使到每个点都有水，求花费最少。花费的计算方法如下：

两点间流通：u->v，花费为 cost = 两点间曼哈顿距离 Y，如果点v的垂直高度高于u还需要加上花费Z
挖井：该点的垂直高度 X

步骤：

  1. 有两种方式可以使一个点有水，那么每个点只要选一种方式即可，不需要两种方式都有（这个最优性很明显）
  2. 除了流通还存在挖井，这个很容易解决，设置一个虚拟顶点0,0指向所有点，边权就是每个点挖井的费用；然后原图上有的边添加进去，就建好图了
  3. 以0为根，求一次最小树形图即可，直接上模板，模板来自小HH，不过时间很悲剧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1020
#define M 1200010
#define INF 0x3f3f3f3f
#define cl memset

int n,X,Y,Z,tot;
struct edge{
    int u,v,w,next;
}e[M+N];
struct vertex{
    int x,y,z;
}a[N];
int in[N],id[N],pre[N],vis[N];

inline void add(int u,int v,int w){
    e[tot].u = u; e[tot].v = v; e[tot++].w = w;
}
inline int abs(int x){
    return x > 0 ? x : -x;
}
inline int dis(int i,int j){
    return abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y) + abs(a[i].z - a[j].z);
}

int Directed_MST(int root,int nv,int ne){
    int ret = 0;
    while(true){
        //1.找最小入边并判断是否能存在最小树形图
        cl(in,0x3f,sizeof(in)); //寻找最小入边，入边数组先初始化INF
        for(int i = 0; i < ne; i++){ //扫描所有边
            int u = e[i].u , v = e[i].v , w = e[i].w;
            if(u != v && w < in[v]){ //更新最小入边并记录前驱
                in[v] = w; pre[v] = u;
            }
        }
        for(int i = 0; i < nv; i++){ //判断是否能构成最小树形图
            if(i == root) continue;
            if(in[i] == INF) return -1; //除根有点没有入边说明不能构成最小树形图
        }

        //2.找环
        int cntnode = 0; //重新建图的顶点标号
        cl(id,-1,sizeof(id)); //重新建图的映射
        cl(vis,-1,sizeof(vis));
        in[root] = 0; //根无入边赋值为0
        for(int i = 0; i < nv; i++){
            ret += in[i]; 
            int v = i;
            while(vis[v] != i && id[v] == -1 && v != root){ //vis用于判环后面两个判断是迭代的终止
                vis[v] = i; v = pre[v];
            }
            if(v != root && id[v] == -1){ //说明上面的迭代是因为有环而终止而不是因为迭代结束
                for(int u = pre[v]; u != v; u = pre[u]) //沿环走一圈，环上缩点为cntnode
                    id[u] = cntnode;
                id[v] = cntnode++;
            }
        }
        if(cntnode == 0) break; //无环找到了最小树形图
        for(int i = 0; i < nv; i++) //将不在环上的点也重新映射为了后面的重新建图
            if(id[i] == -1)
                id[i] = cntnode++;

        //3.重新建图
        for(int i = 0; i < ne; i++){
            int temp = 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[temp];
        }
        nv = cntnode; //新图的点数
        root = id[root]; //重新建图后的根
    }
    return ret;
}

int main(){
    while(scanf("%d%d%d%d",&n,&X,&Y,&Z)!=EOF && (n + X + Y + Z) != 0){
        tot = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            add(0,i,X*a[i].z);
        }
        for(int i = 1; i <= n; i++){
            int m;
            scanf("%d",&m);
            while(m--){
                int j,w;
                scanf("%d",&j);
                if(i == j) continue; //自环
                w = dis(i,j) * Y + (a[j].z > a[i].z ? Z : 0);
                add(i,j,w);
            }
        }
        printf("%d\n",Directed_MST(0,n+1,tot));
    }
    return 0;
}