[UVA][maxflow] 12159 - Gun Fight
|
|
|
The above diagram illustrates sample #1. The imaginary line is represented by the red line passing through two watch towers shown in red. There are 5 gun towers in total. The two groups are represented by two colors blue and black of which blue group is smaller in size. The yellow arrows show the two fights where the black ones get defeated. |
|
|
Here we are in a gun fight again. We have a battlefield similar to a 2-dimensional Cartesian plane. In some of the grid points there are some watch towers. Some of the watch towers have gunmen inside them. Let us denote them as gun towers. The power of each gun tower is given as an integer number P. When a fight takes place between two gun towers, the tower with higher P wins (No result in case of equal P).
Now, there are two opposing groups in the battle. The groups are separated by a boundary line. This boundary line is an imaginary infinite line drawn through two given free watch towers (watch towers without gunmen). The two groups stay in either side of the field. Interestingly, there are always an odd number of gun towers in the field at the start of a battle. This implies that the two groups will be of unequal size. The smaller group wants to adopt a strategy to ensure maximum possible success. A gun tower can fight with at most one of the opposing gun towers. Again, a gun tower can attack an enemy gun tower if the Euclidean distance between them is not greater than a particular distance R. Each gun tower of the smaller group is given the choice to select its opponent.
What is the maximum number of fight the smaller group can win?
Input
There are at most 60 test cases in the input. Every test case starts with an integer N (5≤N≤300), the number of watch towers. Each of the next N lines contains 3 non-negative integers x, y and P. The first two integers (0 ≤ x,y ≤ 10000) denote co-ordinates of the tower. The final integer P (0 ≤ P ≤ 10000) denotes the power of the tower. Note that, a watch tower with P=0 means a free watch tower. The (i+1)th line corresponds to watch tower number i (1 ≤ i ≤ N). Two watch towers will never be placed in the same location.
The next line contains three integers a, b (1 ≤ a,b ≤ N, a!=b) and R (1≤R≤10000), here a and b are the IDs of two free towers to draw the separation line through and meaning of R is given in the problem statement. There will be at least two free towers in the field. There will be no gun towers on the separation line.
The end of input is denoted by a case with N = 0. This case should not be processed.
Output
For each test case, print a line in this format, “Case X: Y”, where X is the case number and Y is the maximum possible number of fight the smaller group can win.
Sample Input Output for Sample Input
|
2 3 3 3 1 2 3 2 0 4 4 4 7 4 0 6 2 1 7 3 6 3 5 50 7 2 3 1 3 1 4 3 2 0 4 4 2 5 3 0 6 2 5 7 3 6 3 5 50 0 |
Case 1: 2 Case 2: 0 |
Problem setter: Mohammad Mahmudur Rahman , Special Thanks: Sohel Hafiz, Rujia Liu
題目描述：
現在有兩團人馬，可以當作城堡互相攻擊。
每座城堡都有戰力指數，而且只能鎖定一名目標攻擊，當然也必須在攻擊半徑內。
而當戰力指數大於另一方戰力指數時，才能宣告獲勝。
求最少城堡的那一方，最多能拿下多少勝利。
輸入時，會給定兩個和平不攻擊的城堡，用以當作一條線劃分兩團人馬。
題目解法：
這裡使用 maxflow 去計算。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
struct Node {
int x, y, v;// x->y, v
int next;
} edge[30005];
int e, head[305], dis[305], prev[305], record[305];
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 n, cases = 0;
int i, j, k;
int x[305], y[305], P[305];
int a, b, R;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
scanf("%d %d %d", &x[i], &y[i], &P[i]);
scanf("%d %d %d", &a, &b, &R);
// ax+by+c = 0
a--, b--;
int ax, by, c;
ax = y[a]-y[b], by = x[b]-x[a], c = -(ax*x[a]+by*y[a]);
vector<int> right, left;
for(i = 0; i < n; i++) {
if(P[i] == 0) continue;
if(ax*x[i]+by*y[i]+c > 0)
right.push_back(i);
else
left.push_back(i);
}
vector<int> big, small;
if(right.size() > left.size())
big = right, small = left;
else
big = left, small = right;
int st = n, ed = n+1;
e = 0;
memset(head, -1, sizeof(head));
for(i = 0; i < small.size(); i++) {
addEdge(st, small[i], 1);
for(j = 0; j < big.size(); j++) {
if(P[small[i]] > P[big[j]]) {
if((x[small[i]]-x[big[j]])*(x[small[i]]-x[big[j]])+
(y[small[i]]-y[big[j]])*(y[small[i]]-y[big[j]]) <= R*R)
addEdge(small[i], big[j], 1);
}
}
}
for(i = 0; i < big.size(); i++)
addEdge(big[i], ed, 1);
printf("Case %d: %d\n", ++cases, maxflow(st, ed));
}
return 0;
}