2015年ACM/ICPC合肥赛区 E题（二分图最大点独立集）
题意：（真tm难读）给你一个n*m的土地，每个方格'.'表示空地，数字表示远古土地（一个连通块），然后你现在要建立牧场，可以建在空地上，也可以建在远古土地上（那么这个数字形成的连通块就是一个牧场），要求相邻的两个牧场不能相邻，求最多可以建多少牧场。
注意 输入的时候n m之间是有空格的。
思路：一看就是有关二分图最大匹配的。。。比赛的时候写了爆搜TLE，赛后补了2个小时莫名其妙WA。。。然后参考了网上的题解。思路完全正确，可能是细节出错误了吧。
因为一旦选定一个数字建牧场，那么包含这个数字的连通块都要建造牧场。所以枚举每个数字(不超过10)的建造情况，然后筛选合法状态，对合法状态下的空地，向其他空地和没建造牧场的远古土地建边（此处直接将二分图翻倍，求得最大匹配数/2）。
然后答案=空土地数量-最大匹配数/2+选定的数字个数。
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int maxn=150;
char s[maxn][maxn];
vector<pii>v[12];
int vis[12],dxy[]={0,1,0,-1,1,0,-1,0};
bool book[12][12];
int mp[12][12];
// 二分图最大匹配模板
struct Max_Match
{
int n;
vector<int>g[maxn];
bool vis[maxn];
int left[maxn];
void init(int n)
{
this->n=n;
for(int i=0;i<=n;i++) g[i].clear();
memset(left,-1,sizeof(left));
}
bool match(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=true;
if(left[v]==-1||match(left[v]))
{
left[v]=u;
return true;
}
}
}
return false;
}
int solve()
{
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(match(i)) ans++;
}
return ans;
}
}MM;
int main()
{
int T,cas=1,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=0;i<=10;i++) v[i].clear();
memset(vis,0,sizeof(vis));
//给含数字的方格编号，并记录其连通块的所有点
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j]>='0'&&s[i][j]<='9')
{
if(!vis[(s[i][j]&15)])
vis[(s[i][j]&15)]=++cnt;
v[vis[(s[i][j]&15)]].push_back(pii(i,j));
}
}
//枚举每个数字选或不选的状态 2的10次方
int stu=(1<<cnt)-1,cou,ans=0;
for(int i=0;i<=stu;i++)
{
cou=0;
memset(book,0,sizeof(book));
for(int j=0;j<cnt;j++)
{
//选的连通块及其周围的空地都标记为不可选
if(i&(1<<j))
{
cou++;
for(int k=0;k<v[j+1].size();k++)
{
int x=v[j+1][k].first;
int y=v[j+1][k].second;
book[x][y]=true;
for(int ii=0;ii<4;ii++)
{
int nx=x+dxy[ii];
int ny=y+dxy[ii+4];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(s[nx][ny]=='.') book[nx][ny]=true;
}
}
}
else
{
//没选的数字就标记不可选
for(int k=0;k<v[j+1].size();k++)
{
int x=v[j+1][k].first;
int y=v[j+1][k].second;
book[x][y]=true;
}
}
}
//判断是否有两个选择的数字块相邻
bool flag=false;
for(int j=0;j<cnt;j++)
{
if(i&(1<<j))
{
for(int k=0;k<v[j+1].size();k++)
{
int x=v[j+1][k].first;
int y=v[j+1][k].second;
for(int ii=0;ii<4;ii++)
{
int nx=x+dxy[ii];
int ny=y+dxy[ii+4];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(s[nx][ny]=='.') continue;
int t=vis[(s[nx][ny]&15)];
if(i&(1<<(t-1)))
{
if(vis[(s[nx][ny]&15)]==vis[(s[x][y]&15)]) continue;
flag=true;
}
}
}
}
}
if(flag) continue;
//给剩下的可选空地重新标号
int cnt=0;
memset(mp,0,sizeof(mp));
for(int r=1;r<=n;r++)
for(int c=1;c<=m;c++)
{
if(s[r][c]=='.'&&!book[r][c])
mp[r][c]=++cnt;
}
MM.init(cnt);
//建边，将原图翻倍，求得最大匹配数/2
for(int r=1;r<=n;r++)
for(int c=1;c<=m;c++)
if(s[r][c]=='.'&&!book[r][c])
{
for(int k=0;k<4;k++)
{
int nx=r+dxy[k];
int ny=c+dxy[k+4];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(s[nx][ny]=='.'&&!book[nx][ny])
{
MM.g[mp[r][c]].push_back(mp[nx][ny]);
}
}
}
for(int r=1;r<=n;r++)
for(int c=1;c<=m;c++)
if(s[r][c]=='.'&&!book[r][c])
{
for(int k=0;k<4;k++)
{
int nx=r+dxy[k];
int ny=c+dxy[k+4];
if(nx<1||nx>n||ny<1||ny>m) continue;
//空地和没选的数字块也可以建边
if(s[nx][ny]!='.')
{
int tmp=vis[(s[nx][ny]&15)]-1;
if(i&(1<<tmp)) continue;
MM.g[mp[r][c]].push_back(mp[nx][ny]);
}
}
}
int tmp=cnt-MM.solve()/2;
//答案=可选总点数-最大匹配/2+已选数字块个数
ans=max(ans,tmp+cou);
}
printf("Case #%d: %d\n",cas++,ans);
}
return 0;
}