HDU-1045 Fire Net(简单缩点+最大匹配)
题意：
给出n(<=4)，然后n行n列点，'X'代表墙，'.'代表空地，现需要往图中的空地放一些炮楼，两个炮楼不能同时在同一行或者同一列除非两个炮楼之间存在墙。求最大放置炮楼的数量。思路：
刚开始尝试最大独立集，但是互相限制的点构图构不成二分图，尝试直接最大匹配也是构不成二分图。然后看到别人思路发现可以进行缩点，即在一行或一列若干个空地构成一个大空地，显然这若干个点中最多只能放一个点，所以进行按行分区和按列分区，两种分区分别都是包括了全部空地的划分(注意是分别而非一起)。
那么每个行连通块确保了该块内只选择一个，而与其相交的列连通块则表示选择当前行连通块的某一块空地的同时必须也要选择该块空地连带的列连通块，则这样就符合了二分图中边的性质了，从而我们对构造的二分图求最大匹配就是答案了。
代码：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;
char mp[5][5];
int g[25][25];
int n, cnt, ans;
int match[25], vis[25];
vector<int> bl[25][2];
int use[25][2];
int dfs(int cur)
{
for(int i = 0; i <= cnt; ++i)
{
if(!g[cur][i] || vis[i]) continue;
vis[i] = 1;
if(match[i] == -1 || dfs(match[i]))
{
match[i] = cur;
return 1;
}
}
return 0;
}
int main()
{
while(~scanf("%d", &n) && n)
{
memset(g, 0, sizeof g); cnt = 0;
memset(match, -1, sizeof match);
memset(use, 0, sizeof use);
for(int i = 0; i < n*n; ++i) bl[i][0].clear(), bl[i][1].clear();
for(int i = 0; i < n; ++i) scanf("%s", mp[i]);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
{
if(mp[i][j] == 'X') continue;
if(!use[i*n+j][0])
{
int k = i; ++cnt;
while(k < n && mp[k][j] == '.')
{
use[k*n+j][0] = 1;
bl[k*n+j][0].push_back(cnt);
++k;
}
}
if(!use[i*n+j][1])
{
int k = j; ++cnt;
while(k < n && mp[i][k] == '.')
{
use[i*n+k][1] = 1;
bl[i*n+k][1].push_back(cnt);
++k;
}
}
}
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
{
int k = i*n+j;
for(int ii = 0; ii < bl[k][0].size(); ++ii)
for(int jj = 0; jj < bl[k][1].size(); ++jj)
{
g[bl[k][0][ii]][bl[k][1][jj]] = 1;
g[bl[k][1][jj]][bl[k][0][ii]] = 1;
}
}
ans = 0;
for(int i = 1; i <= cnt; ++i)
{
memset(vis, 0, sizeof vis);
if(dfs(i)) ++ans;
}
printf("%d\n", ans/2);
}
return 0;
}
继续加油~