[UVA][二分+maxflow二分匹配] 10804 - Gopher Strategy
Gopher Strategy
Time Limit: 3 seconds
| Agent Cooper: "Look at that! Ducks... on the lake!" |
Gophers like to feed in the field, but they always have to look out for hawks that might hunt them. A group of gophers have decided to get more organized and need your help developing an escape strategy in case of a hawk attack.
Given the coordinates of m gophers and n holes in the field, what is the minimum time required for each gopher to reach a hole (at most one gopher per hole)? Every gopher runs in a straight line at a speed of 1 unit per second, and the group can tolerate the loss of at most k gophers. (Gophers are lost when they do not have enough time to reach an empty hole.)
Input
The first line of input gives the number of cases, N.
N test cases follow. Each one starts with a line containing
the integers m, n and k
(0 <= m, n <= 50, 0 <= k <= m).
The next m lines will give the x,y-coordinates of the gophers.
The n lines after that will give the coordinates of the holes.
Output
For each test case, output the line "Case #x:", where x is the
number of the test case. Then print the minimum number of seconds required
for at least m-k gophers to reach a hole, rounded to 3 decimal
places. Every answer will obey the formula
fabs(ans*1e3 - floor(ans*1e3) - 0.5) > 1e-2
Print "Too bad." if there is no solution. Print an empty line after each test case.
| Sample Input | Sample Output |
4 3 3 1 0 0 1 0 2 0 0 1 1 1 2 1.5 3 3 1 0 1 1 2 2 1 1 0 1 1 2 0 3 3 0 0 1 1 2 2 1 1 0 1 1 2 0 1 0 0 100.0 200.5 |
Case #1: 1.000 Case #2: 1.000 Case #3: 1.414 Case #4: Too bad. |
Problemsetter: Igor Naverniouk
Alternate solutions: Yury Kholondyrev, Bartholomew Furrow
題目說明：
給定老鼠座標跟洞座標，一個洞最多一隻老鼠，現在有老鷹要來抓他們。
而老鼠最多可以被老鷹抓走 k 隻，即損失 k 隻。
問最後抵達洞口的老鼠的時間最小化為多少？
題目分析：
由於一個洞最多一隻老鼠，很明顯地想到二分圖匹配，
因此我們二分搜尋答案，限定可以連接的鼠-洞，只要匹配數大於等於 n-k，
那麼就下修答案，否則將上修。
這裡匹配使用 maxflow。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
int x, y, v;// x->y, v
int next;
} edge[10005];
int e, head[105], dis[105], prev[105], record[105];
void addEdge(int x, int y, int v) {
edge[e].x = x, edge[e].y = y, edge[e].v = v;
edge[e].next = head[x], head[x] = e++;
edge[e].x = y, edge[e].y = x, edge[e].v = 0;
edge[e].next = head[y], head[y] = e++;
}
int maxflow(int s, int t) {
int flow = 0;
int i, j, x, y;
while(1) {
memset(dis, 0, sizeof(dis));
dis[s] = 0xffff; // oo
queue<int> Q;
Q.push(s);
while(!Q.empty()) {
x = Q.front();
Q.pop();
for(i = head[x]; i != -1; i = edge[i].next) {
y = edge[i].y;
if(dis[y] == 0 && edge[i].v > 0) {
prev[y] = x, record[y] = i;
dis[y] = min(dis[x], edge[i].v);
Q.push(y);
}
}
if(dis[t]) break;
}
if(dis[t] == 0) break;
flow += dis[t];
for(x = t; x != s; x = prev[x]) {
int ri = record[x];
edge[ri].v -= dis[t];
edge[ri^1].v += dis[t];
}
}
return flow;
}
double nx[100], ny[100], mx[100], my[100];
double g[100][100];
int n, m, k;
int i, j;
int solve(double limit) {
e = 0;
memset(head, -1, sizeof(head));
for(i = 0; i < n; i++) {
addEdge(0, i+1, 1);
for(j = 0; j < m; j++) {
if(g[i][j] <= limit)
addEdge(i+1, j+n+1, 1);
}
}
for(i = 0; i < m; i++)
addEdge(i+n+1, n+m+1, 1);
int flow = maxflow(0, n+m+1);
if(flow >= n-k)
return 1;
return 0;
}
int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &n, &m, &k);
for(i = 0; i < n; i++)
scanf("%lf %lf", &nx[i], &ny[i]);
for(i = 0; i < m; i++)
scanf("%lf %lf", &mx[i], &my[i]);
double l = sqrt(pow(nx[0]-mx[0],2)+pow(ny[0]-my[0],2)), r = 0, mid;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
g[i][j] = sqrt(pow(nx[i]-mx[j],2)+pow(ny[i]-my[j],2));
l = min(l, g[i][j]);
r = max(r, g[i][j]);
}
}
printf("Case #%d:\n", ++cases);
if((n == 0 && m == 0) || (n == k) || n == 0)
puts("0.000");
else if(n-k > m)
puts("Too bad.");
else {
#define eps 1e-5
int cnt = 0;
while(fabs(l-r) > eps && cnt < 100) {
mid = (l+r)/2;
int f = solve(mid);
if(f == 0)
l = mid;
else
r = mid;
cnt++;
}
printf("%.3lf\n", l);
}
puts("");
}
return 0;
}/*
4
3 3 1
0 0
1 0
2 0
0 1
1 1
2 1.5
3 3 1
0 1
1 2
2 1
1 0
1 1
2 0
3 3 0
0 1
1 2
2 1
1 0
1 1
2 0
1 0 0
100.0 200.5
*/