UVa 10349 Antenna Placement

題意：
    如題目的圖，一個圓圈最多能圈住兩個'*'，現在問一幅圖有n個'*'，最少用多少個圓圈就能把所有'*'圈住？

想法：
    最大匹配問題，將圖上所有點分成兩群相間隔，例如
101010
010101
101010
    在編號1的'*'建一條邊連到S(Super Source)，在編號'0'的'*'建一條邊連到T(Super Sink )，然後相鄰的'*'彼此也建一條邊，這些邊的容量都是1，建完邊後套一次最大流模板，就是最大匹配數。
    做最大匹配得到的結果不是真正的答案，例如*****五個'*'的最大匹配是2，答案則是(5-3)，因此本題答案為(所有'*'數量-最大匹配數)。

	#include <cstdio>
	#include <cstring>
	#include <queue>
	#include <algorithm>
	using namespace std;
	int cap[500][500], flow[500][500];
	int bottleneck[500], pre[500];
	int main()
	{
	int n, h, w;
	char grid[50][15];
	scanf("%d", &n);
	while (n--) {
	scanf("%d %d", &h, &w);
	// Initial
	int S = h*10+w,
	T = h*10+w+1;
	memset(cap, 0, sizeof(cap));
	memset(flow, 0, sizeof(flow));
	int numOfStar = 0;
	// Input
	for (int i = 0; i < h; ++i)
	scanf("%s", grid[i]);
	// Build Graph
	for (int i = 0; i < h; ++i) {
	for (int j = 0; j < w; ++j) {
	if (grid[i][j] == '*') {
	++numOfStar;
	if ((i+j) % 2) {
	cap[S][i*10+j] = 1;
	if (i>0 && grid[i-1][j] == '*') cap[i*10+j][(i-1)*10+j] = 1;
	if (j>0 && grid[i][j-1] == '*') cap[i*10+j][i*10+j-1] = 1;
	if (i+1<h && grid[i+1][j] == '*') cap[i*10+j][(i+1)*10+j] = 1;
	if (j+1<w && grid[i][j+1] == '*') cap[i*10+j][i*10+j+1] = 1;
	}
	else cap[i*10+j][T] = 1;
	}
	}
	}
	// Maximum Flow
	int result = 0;
	while (1) {
	memset(bottleneck, 0, sizeof(bottleneck));
	queue<int> Q;
	Q.push(S);
	bottleneck[S] = 999999999;
	while (!Q.empty()) {
	int now = Q.front(); Q.pop();
	for (int nxt = 0; nxt <= T; ++nxt) {
	if (bottleneck[nxt] == 0 && cap[now][nxt] > flow[now][nxt]) {
	Q.push(nxt);
	pre[nxt] = now;
	bottleneck[nxt] = min(bottleneck[now], cap[now][nxt] - flow[now][nxt]);
	}
	}
	}
	if (bottleneck[T] == 0) break;
	for (int now = T; now != S; now = pre[now]) {
	flow[pre[now]][now] += bottleneck[T];
	flow[now][pre[now]] -= bottleneck[T];
	}
	result += bottleneck[T];
	}
	printf("%d\n",numOfStar - result);
	}
	}

view raw [UVa] 10349 Antenna Placement.cpp hosted with ❤ by GitHub