[UVA][幾何&最大流] 11757 - Winger Trial
|
F |
Winger Trial |
|
After the great winger Donaldo left his soccer team, coach sir Thelex has found himself in a great fix. The strength of his team is reduced greatly and he needs to find a suitable replacement immediately. The coach selects a number of young wingers from around the world and sets up a trial for them.
The trial will take place on a rectangular shaped field of length L meters & width W meters. There are N robot defenders placed on the field. The defenders do not change their positions but if a winger's distance from a defender is not more than d meters, it will automatically tackle him. A robot defender may tackle at most once. On the beginning of the trial, a winger stands on the left edge of the field (across the length) with a soccer ball. Now, his task is to avoid the obstructions of the robot defenders and reach the rightmost edge of the field with the ball. Please tell him the minimum number of tackles he must face in order to reach the opposite end. A player must not go outside the field or he will be disqualified.
Input
Every test case begins with 4 integers, L (1<=L<=10000), W (1<=W<=10000), N (1<=N<=100) & d (1<=d<=1000), as described above. Each of the following N lines contain 2 integers each, defining the x & y co-ordinates of a defender. You can consider the co-ordinate of the lower-left corner of the field to be (0,0) and upper-right corner to be (L,W). Obviously, all the defenders are located inside the field.
The end of input will be marked by a case with L=W=N=d=0. This case should not be processed.
Output
For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the minimum number of tackles that needs to be dealt with.
|
Sample Input |
Sample Output |
|
500 300 5 100 |
Case 1: 1 |
Problem Setter: Mohammad Mahmudur Rahman, Special Thanks: Manzurur Rahman Khan
題目描述：
一個足球員和一群擬真的機器人，每個機器人的勢力範圍限定一個圓，
問足球員最少要進行幾次剷球，才能將球從左邊運道右邊。
題目解法：
一樣打算將這些機器人當作節點，而考慮將可以防守的兩點連線。
同時上下兩邊也各當作一點看待。
此時最少剷球次數即該圖的最小割，但必須知道剷球一次是跨越一個機器人，也就是權重是放在點上的。
最小割 = 最大流
#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[30005];
int e, head[205], dis[205], prev[205], record[205];
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;
}
int main() {
int L, W, N, d;
int i, j, k, cases = 0;
int x[105], y[105];
while(scanf("%d %d %d %d", &L, &W, &N, &d) == 4) {
if(L+W+N+d == 0)
break;
e = 0;
memset(head, -1, sizeof(head));
for(i = 0; i < N; i++)
scanf("%d %d", &x[i], &y[i]);
int st = 2*N, ed = 2*N+1;
for(i = 0; i < N; i++) {
addEdge(i*2, i*2+1, 1);
if(y[i] <= d)
addEdge(st, i*2, 1);
if(W-y[i] <= d)
addEdge(i*2+1, ed, 1);
for(j = 0; j < N; j++) {
if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) <= 4*d*d)
addEdge(i*2+1, j*2, 1);
}
}
int flow = maxflow(st, ed);
printf("Case %d: %d\n", ++cases, flow);
}
return 0;
}