2014-01-24 11:48:27Morris
[ZJ][二分貪婪] a692 區域劃分
內容 ：
天又酷國有 n 個城市，這些城市以 n-1 條道路相連，且彼此可透過這些道路互相到達。天又酷國國王是個蘿莉控，經過調查，他知道每個城市的蘿莉數。他現在要把他的國家分成 k 個區域，區域內任兩個城市往來不需經過區域外的城市。假設劃分後，各個區域內的蘿莉數為 a1, a2, ..., ak，他希望 min{ai | 1 ≦ i ≦ k} 的值越大越好。請問 min{ai | 1 ≦ i ≦ k} 最大為何？
輸入說明 ：
第一行有兩個數字 n, k，代表天又酷國的城市數目和天又酷國國王想劃分出的區域數。
第二行有 n 個正整數 l1, l2, ..., ln，代表各個城市的蘿莉數。
接下來的 n-1 行，每行有兩個正整數 u, v，代表有一條道路連接城市 u 和城市 v。
1 ≦ k ≦ n ≦ 1,000,000
li ≦ 100,000,000
輸出說明 ：
請輸出所有劃分方式中 min{ai | 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
範例輸出 ：
10
提示 ：
將 {1, 3, 7} 劃在同一區域，{2, 4, 5, 6, 9} 劃在同一區域，{8, 10, 11, 12} 劃在同一區域，可得 min{ai | 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
*/
#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
*/
您好!這位高手請問可以附上註解嗎?感激不盡
是用tree嗎