Morris' Blog

2014-01-24 11:48:27Morris

[ZJ][二分貪婪] a692 區域劃分

留言 2 收藏 0 推薦 0

內容：

天又酷國有 n 個城市，這些城市以 n-1 條道路相連，且彼此可透過這些道路互相到達。天又酷國國王是個蘿莉控，經過調查，他知道每個城市的蘿莉數。他現在要把他的國家分成 k 個區域，區域內任兩個城市往來不需經過區域外的城市。假設劃分後，各個區域內的蘿莉數為 a₁, a₂, ..., a_k，他希望 min{a_i| 1 ≦ i ≦ k} 的值越大越好。請問 min{a_i| 1 ≦ i ≦ k} 最大為何？

輸入說明：

第一行有兩個數字 n, k，代表天又酷國的城市數目和天又酷國國王想劃分出的區域數。

第二行有 n 個正整數 l₁, l₂, ..., l_n，代表各個城市的蘿莉數。

接下來的 n-1 行，每行有兩個正整數 u, v，代表有一條道路連接城市 u 和城市 v。

1 ≦ k ≦ n ≦ 1,000,000

l_i ≦ 100,000,000

輸出說明：

請輸出所有劃分方式中 min{a_i| 1 ≦ i ≦ k} 的最大值。

範例輸入：

12 3
10 9 1 3 9 9 1 4 6 1 2 3
1 2
2 4
2 5
2 6
4 9
1 3
3 7
3 8
8 10
8 11
8 12

範例輸出：

提示：

將 {1, 3, 7} 劃在同一區域，{2, 4, 5, 6, 9} 劃在同一區域，{8, 10, 11, 12} 劃在同一區域，可得 min{a_i| 1 ≦ i ≦ k} 的最大值 10。

出處：

STEP5 的蘿莉 (管理：xavier13540)

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
#define maxN 1048576
int n, m, w[maxN];
int bfs_order[maxN], g_1[maxN];
long long g_2[maxN];
struct Node {
    int to, pass;
    int next;
} edge[maxN*2];
int e, head[maxN];
void addEdge(int x, int y) {
    edge[e].to = y, edge[e].pass = 1;
    edge[e].next = head[x], head[x] = e++;
    edge[e].to = x, edge[e].pass = 1;
    edge[e].next = head[y], head[y] = e++;
}
void bfs(int st) {
    queue<int> q;
    int idx = 0, x, y;
    q.push(st), bfs_order[idx++] = st;
    while(!q.empty()) {
        x = q.front(), q.pop();
        for(int i = head[x]; i != -1; i = edge[i].next) {
            if(edge[i].pass) {
                q.push(edge[i].to);
                bfs_order[idx++] = edge[i].to;
                edge[i^1].pass = 0;
            }
        }
    }
}
int greedy(long long group) {
    for(int i = n-1; i >= 0; i--) {
        int x = bfs_order[i];
        g_1[x] = g_2[x] = 0;
        int &gcnt = g_1[x];
        long long &ghas = g_2[x];
        for(int j = head[x]; j != -1; j = edge[j].next) {
            if(edge[j].pass) {
                gcnt += g_1[edge[j].to];
                ghas += g_2[edge[j].to];
            }
        }
        ghas += w[x];
        if(ghas >= group)
            ghas = 0, gcnt++;
        if(gcnt >= m)
            return 1;
    }
    //printf("group %d, %d\n", group, g_1[1]);
    return 0;
}
void binary_greedy() {
    long long sum = 0;
    for(int i = 1; i <= n; i++)
        sum += w[i];
    long long l = 0, r = sum / m, mid;
    long long ret = 0;
    while(l <= r) {
        mid = (l + r)/2;
        if(greedy(mid))
            l = mid + 1, ret = mid;
        else
            r = mid - 1;
    }
    printf("%lld\n", ret);
}
int main() {
    while(scanf("%d %d", &n, &m) == 2) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        e = 0;
        memset(head, -1, sizeof(head));
        int x, y;
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            addEdge(x, y);
        }
        bfs(1); // rooted tree
        //for(int i = 0; i < n; i++)
        //    printf("b %d\n", bfs_order[i]);
        binary_greedy();
    }
    return 0;
}
/*
12 3
10 9 1 3 9 9 1 4 6 1 2 3
1 2
2 4
2 5
2 6
4 9
1 3
3 7
3 8
8 10
8 11
8 12

10
*/

上一篇：[ZJ] a764、a768、a779

下一篇：[ZJ][單調堆] a813 2013高雄市能力競賽高中組 4. 城市觀測