一个简单的二分构图题,因为以前做过更难的,所以这次很轻松的就AC了,不过关于求关键格子的那个思路还是在网上看的,水平还是很菜啊~~
把横坐标和纵坐标分别看做两个点集,某个格子能放车的话就在对应的横纵坐标之间连一条边,这样,二分图就建好了。明显的,每一条边都代表一个车,要求能最多放的车数也就等价于求二分最大匹配了。而对于关键格子,由于关键格子是指,少了这个格子后就放不了最多的车数了,因此,将棋盘中的某个格子删去,若还能求出原来的最大匹配数,则说明该格子不是关键格子,反之就是了。
代码如下:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
const int M=1010;
const int N=210;
bool g[N][N],vis[N];
int n,m,k,ans,match[N];
int u[N],v[N],first[N],next[N];
void build()
{
memset(first,-1,sizeof(first));
int i;
for (i=0;i<k;i++) {
scanf("%d%d",u+i,v+i);
next[i]=first[u[i]];
first[u[i]]=i;
}
}
bool dfs(int x,int tag)
{
int i,j;
for (i=first[x];i!=-1;i=next[i]) if (!vis[v[i]] && tag!=i)
{
vis[v[i]]=true;
if (match[v[i]]==-1 || dfs(match[v[i]],tag)){
match[v[i]]=x;
return true;
}
}
return false;
}
int get(int e)
{
int t=0;
memset(match,-1,sizeof(match));
for (int i=1;i<=n;i++) {
memset(vis,false,sizeof(vis));
if (dfs(i,e)) t++;
}
if (t==ans) return false;
else return true;
}
int main()
{
int i,j,T=1;
while(~scanf("%d%d%d",&n,&m,&k))
{
build();
ans=0;
memset(match,-1,sizeof(match));
for (i=1;i<=n;i++) {
memset(vis,false,sizeof(vis));
if (dfs(i,-1)) ans++;
}
int sum=0;
for (i=1;i<=n;i++) {
for (j=first[i];j!=-1;j=next[j]) if (get(j)) sum++;
}
printf("Board %d have %d important blanks for %d chessmen.\n",T++,sum,ans);
}
}