24h購物| | PChome| 登入
2013-04-27 12:02:19| 人氣788| 回應0 | 上一篇 | 下一篇

[UVA][二分+maxflow二分匹配] 10804 - Gopher Strategy

推薦 0 收藏 0 轉貼0 訂閱站台

Problem ?
 Gopher Strategy
 Time Limit: 3 seconds

Agent Cooper: "Look at that! Ducks... on the lake!"
Harley Peyton, "Twin Peaks."

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
*/

我要檢舉
#10804#Gopher Strategy#二分答案#maxflow#二分匹配
台長： Morris

您可能對以下文章有興趣

人氣(788) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][幾何、半平面交] 10084 - Hotter Colder
此分類上一篇:[UVA][Trie] 10745 - Dominant Strings

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文