解題區/解題區 - UVa

UVa 12587 - Reduce the Maintenance Cost

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在 N 個城市，每個城市都要每月的基礎花費，而在城市之間有 M 條邊，市長安排在邊兩側的城市其一要負責維護這一條重要邊，而重要邊的維護花費為該邊移除後，導致任兩個城市之間無法相連的對數乘上該路長。

只需要將一條邊交給相鄰的其一城市維護即可，因此會將該城市的月花費上升，求一種分配方案使得城市的最大花費最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
2 1
5 10
1 2 10
  
6 6
10 20 30 40 50 60
1 2 1
2 3 1
1 3 1
1 4 6
1 5 6
4 6 2
  
3 1
10 20 30
2 3 1

Sample Output

1
2
3
Case 1: 15
Case 2: 80
Case 3: 30

Solution

首先，重要邊只有 bridge 需要維護，除了 bridge 外，不會造成任兩個點之間不連通的情況。

因此將所有 bridge 求出，建造出森林 (很多棵 tree)，接著二分最大花費，然後用貪心算法驗證答案是否可行。貪心的步驟採用先把葉節點的花費最大化，如果無法將維護成本放置到葉節點，則必然需要將維護成本交給其父節點，然後將所有葉節點移除。持續遞歸檢查。

當然可以選擇對每一個樹二分最大花費，取最大值即可。這麼寫要看當初怎麼設計，否則會挺痛苦的。

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
    int x, y, s;
    long long w;
    edge(int a=0, int b=0, long long c=0, int d=0):
        x(a), y(b), w(c), s(d) {}
};
vector<edge> g[32767];
int visited[32767], depth[32767], back[32767];
vector<edge> bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    back[u] = 0x3f3f3f3f;
    int sz = 1, t;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].y;
        if(v == p)	continue;
        if(!visited[v]) {
            t = findBridge(v, u, dep+1);
            sz += t;
            if(back[v] > dep)
                bridge.push_back(edge(u, v, g[u][i].w, t));
            back[u] = min(back[u], back[v]);
        } else {
            back[u] = min(back[u], depth[v]);
        }
    }
    return sz;
}
vector<edge> tree[32767];	
long long node_w[32767], place_w[32767];
int dfs(int u, long long mx_w, int p, long long p_w) {
    visited[u] = 1;
    for (int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i].y;
        if (visited[v] == 0) {
            if (!dfs(v, mx_w, u, tree[u][i].w))
                return 0;
        }
    }
    if (place_w[u] + p_w <= mx_w)
        place_w[u] += p_w;
    else
        place_w[p] += p_w;
    if (place_w[u] > mx_w)
        return 0;
    return 1;
        
}
int check(long long mx_w, int n) {
    for (int i = 1; i <= n; i++)
        visited[i] = 0, place_w[i] = node_w[i];
    int ok = 1;
    for (int i = 1; i <= n && ok; i++) {
        if (visited[i] == 0) {
            ok &= dfs(i, mx_w, 0, 0);
        }
    }
//	printf("check %d ok %d\n", mx_w, ok);
    return ok;
}
int main() {
    int testcase, cases = 0, n, m, x, y, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        
        long long sum = 0, low_w = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &node_w[i]);
            g[i].clear(), tree[i].clear();
            sum += node_w[i], low_w = max(low_w, node_w[i]);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(edge(x, y, w));
            g[y].push_back(edge(y, x, w));
        }
        
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                bridge.clear();
                int comp_size = findBridge(i, -1, 0);
                for (int j = 0; j < bridge.size(); j++) {
                    long long N = (long long) bridge[j].s * (comp_size - bridge[j].s);
                    tree[bridge[j].x].push_back(edge(bridge[j].x, bridge[j].y, bridge[j].w * N));
                    tree[bridge[j].y].push_back(edge(bridge[j].y, bridge[j].x, bridge[j].w * N));
                    sum += bridge[j].w * N;
//					printf("%d %d - %d\n", bridge[j].x, bridge[j].y, bridge[j].w * N);
                }
            }
        }
        
        // binary search answer
        long long l = low_w, r = sum, mid, ret;
        while (l <= r) {
            mid = (l + r)/2;
            if (check(mid, n))
                r = mid - 1, ret = mid;
            else
                l = mid + 1;
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
3
2 1
5 10
1 2 10
6 6
10 20 30 40 50 60
1 2 1
2 3 1
1 3 1
1 4 6
1 5 6
4 6 2
3 1
10 20 30
2 3 1
9999
3 3
4 5 6
1 2 1
2 3 1
3 1 1
*/