[UVA][maxflow] 11419 - SAM I AM
Problem C
SAM I AM
Input: Standard Input
Output: Standard Output
The world is in great danger!! Mental's forces have returned to Earth to eradicate humankind. Our last hope to stop this great evil is Sam “Serious” Stone. Equipped with various powerful weapons, Serious Sam starts his mission to destroy the forces of evil.
After fighting two days and three nights, Sam is now in front of the temple KOPTOS where Mental's general Ugh Zan III is waiting for him. But this time, he has a serious problem. He is in shortage of ammo and a lot of enemies crawling inside the temple waiting for him. After rounding the temple Sam finds that the temple is in rectangle shape and he has the locations of all enemies in the temple.
All
of a sudden he realizes that he can kill the enemies without entering the
temple using the great cannon ball which spits out a gigantic ball bigger than
him killing anything it runs into and keeps on rolling until it finally
explodes. But the cannonball can only shoot horizontally or vertically and all
the enemies along the path of that cannon ball will be killed.
Now he wants to save as many cannon balls as possible for fighting with Mental. So, he wants to know the minimum number of cannon balls and the positions from which he can shoot the cannonballs to eliminate all enemies from outside that temple.
Input
Here, the temple is defined as a RXC grid. The first line of each test case contains 3 integers: R(0<R<1001), C(0<C<1001) representing the grid of temple (R means number of row and C means number of column of the grid) and the number of enemies N(0<N<1000001) inside the temple. After that there are N lines each of which contains 2 integers representing the position of the enemies in that temple. Each test case is followed by a new line (except the last one). Input is terminated when R=C=N=0. The size of the input file is around 1.3 MB.
Output
For each test case there will be one line output. First print the minimum number (m) of cannonballs needed to wipe out the enemies followed by a single space and then m positions from which he can shoot those cannonballs. For shooting horizontally print “r” followed by the row number and for vertical shooting print “c” followed by the column number. If there is more than one solution any one will do.
Sample Input Output for Sample Input
|
4 4 3 1 1 1 4 3 2
4 4 2 1 1 2 2
0 0 0
|
2 r1 r3 2 r1 r2
|
Problemsetter: Syed Monowar Hossain
Special Thanks: Derek Kisman
這題挺特別的，在建圖構思上，希望用最少的點覆蓋所有可能，圖形可以湊成二分圖。
至於邊的關係，我們將其 row 當作 X 集，column 當作 Y 集，那麼當一個節點(x, y)存在要被覆蓋的話，則將從 x 拉到 y，因此在圖形上肯定是二分圖。
那問題便成用最少點覆蓋所有的邊，在二分圖中，最大匹配數 = 最少點覆蓋的點數。
每條匹配的兩端，必然一定會存在一點是最少點覆蓋中的點。仔細思考一下，不會同時有兩端都在其中。
至於要少麼在匹配後找到最少點覆蓋的那些點？直接從 X 集沒有被匹配的點出發，找出一條交錯路，將所有點標記。
最後輸出在 X 集中沒有被標記的的點、Y 集被標記的點就是答案。
#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[2010005];
int e, head[2005], dis[2005], prev[2005], record[2005];
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 mx[1001], my[1001];
int X[1001], Y[1001];
int r, c, n, x, y;
int i, j, k;
void dfs(int nd) {
if(X[nd]) return;
X[nd] = 1;
int i;
for(i = head[nd]; i != -1; i = edge[i].next) {
if(edge[i].y) {// not source
if(my[edge[i].y-r] != -1) {
Y[edge[i].y-r] = 1;
dfs(my[edge[i].y-r]);
}
}
}
}
int main() {
while(scanf("%d %d %d", &r, &c, &n) == 3) {
if(r+c+n == 0) break;
e = 0;
memset(head, -1, sizeof(head));
int source = 0, sink = r+c+1;
int ux[2005] = {}, uy[2005] = {};
while(n--) {
scanf("%d %d", &x, &y);
ux[x] = 1;
uy[y] = 1;
addEdge(x, r+y, 1);
}
for(i = 1; i <= r; i++) {
if(ux[i])
addEdge(source, i, 1);
}
for(i = 1; i <= c; i++) {
if(uy[i])
addEdge(r+i, sink, 1);
}
int flow = maxflow(source, sink);
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
memset(X, 0, sizeof(X));
memset(Y, 0, sizeof(Y));
for(i = 1; i <= r; i++) {
for(j = head[i]; j != -1; j = edge[j].next) {
if(edge[j].v == 0 && edge[j].y > r) {
mx[i] = edge[j].y-r;
my[edge[j].y-r] = i;
break;
}
}
}
printf("%d", flow);
for(i = 1; i <= r; i++) {
if(ux[i] == 0) continue;
if(mx[i] == -1)
dfs(i);
}
for(i = 1; i <= r; i++)
if(!X[i] && ux[i]) printf(" r%d", i);
for(i = 1; i <= c; i++)
if(Y[i] && uy[i]) printf(" c%d", i);
puts("");
}
return 0;
}