时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇油行业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。
地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水
输入描述:
测试输入包含多条测试数据
测试数据的第一行给出了测试数据的数目T（T<75）
每个测试样例都用数字N（N<50）来表示地图区域的大小，接下来N行，每行都有N个字符，其中符号’.’表示海面、符号’#’表示油面。
输出描述:
输出格式如下“Case X: M”（X从1开始），M是商人可以最多得到的油量。
题意分析：
每次取1*2的长方形区块，问你最多可以取多少次。
思路一：
考察二分图的最大匹配。首先需要对油面进行编号，然后，用邻接表建立二分图，最后就是经典的匈牙利算法的运用。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
char map[N][N];
bool vis[N*N];
int from[N*N]; //Not N!
vector<int> mp[N*N]; //邻接表
void Read(int &n){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%s",map[i]+1);//从地址mp[i][1]开始接收字符串
}
void PreProcess(int n, int &cnt){
//对油量区域编号
int num[N][N];
for(int t=1;t<=n;t++)
for(int r=1;r<=n;r++){
if(map[t][r] == '#')
num[t][r] = ++cnt;
}
for(int i=1;i<=cnt;i++) mp[i].clear(); //清空元素(not n!)
//用邻接表构建二分图
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++){
if(map[k][j] == '#'){
if(k>1 && map[k-1][j]=='#') mp[num[k][j]].push_back(num[k-1][j]);
if(k<n && map[k+1][j]=='#') mp[num[k][j]].push_back(num[k+1][j]);
if(j>1 && map[k][j-1]=='#') mp[num[k][j]].push_back(num[k][j-1]);
if(j<n && map[k][j+1]=='#') mp[num[k][j]].push_back(num[k][j+1]);
}
}
}
bool AgumentPath(int i){
for(int k=0;k<mp[i].size();k++){
int tmp = mp[i].at(k);
if(!vis[tmp]){ //与i关联的点tmp不在增广路上
vis[tmp] = true;
//tmp是未盖点，或从tmp对应项出发有增广路
if(from[tmp]==-1 || AgumentPath(from[tmp])){
from[tmp] = i;
return true;
}
}
}
return false;
}
int Hungary(int cnt){
memset(from,-1,sizeof(from)); //初始值-1表示未盖点
int ans = 0;
for(int i=1;i<=cnt;i++){
memset(vis,false,sizeof(vis));//每次找增广路vis都要init为false
if(AgumentPath(i)) ans ++;
}
return ans;
}
int main(){
int t,n,ans,cnt;
scanf("%d",&t);
for(int i=1;i<=t;i++){
Read(n);
cnt = 0;
PreProcess(n,cnt);
//对每个区域的增广路会多计算一倍，且所有区域合并与分开计算增广路并无差别
ans = Hungary(cnt)/2;
printf("Case %d: %d\n",i,ans);
}
return 0;
}
思路二：
不难发现这样一个规律：在一个二维坐标中，一个位置的横纵坐标之和x+y，与之相邻位置的便是x+y+1或x+y-1，可得任意两个相邻位置其横纵坐标之和必然是一奇一偶。同时我们还发现，只要是1*2这种两个相邻区块的，这两个区块的坐标和必然是一奇一偶配对，所以我们直接统计当前区块下奇数和偶数的个数（ans0, ans1)，显然每次最终能配对的对数必然取决于较小的个数ans+=min(ans0, ans1）注意为了避免重复计算，要踩过的点都把其变成点。
代码：
#include<bits/stdc++.h>
using namespace std;
char ch[55][55];
int n, ans0, ans1;
void dfs(int i, int j)
{
if(i < 0 || j < 0 || i >= n || j >= n || ch[i][j] == '.')
return ;
if((i + j)%2 == 0)
ans0++;
else
ans1++;
ch[i][j] = '.';
dfs(i, j-1);
dfs(i, j+1);
dfs(i+1, j);
dfs(i-1, j);
}
int main()
{
int T, i, j, ans;
ios::sync_with_stdio(false);
cin >> T;
for(int t = 1; t <= T; ++t){
memset(ch, 0, 55*55*sizeof(char));
ans = 0;
cin >> n;
for(i = 0; i < n; ++i)
cin >> ch[i];
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
if(ch[i][j] == '#'){
ans0 = ans1 = 0;
dfs(i, j);
ans += min(ans0, ans1);
}
cout << "Case " << t << ": " << ans << endl;
}
return 0;
}
参考：
二分图匹配博客
