二分图求最大匹配

我们以每一个格子为边，以行和列为两个集合，那么求二分图的最大匹配数就是最多能放车的数目，那么什么是重要点呢？就是删掉后会影响最大匹配数的匹配边。

我们求出最大匹配数后，枚举匹配边，将其删掉后，从x集合的每一个未匹配元素出发，找增广路，如果找不到，就说明这是一个重要点。

注意:在寻找增广路的时候,一定不能改变原有的match数组

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return rv*fh;

}

int m,n,k,dt[105][105],g[105][105],match[105];

bool f[105],tag[105][105],bj[105];

bool hungarian(int u,bool flag){

	for(int i=1;i<=g[u][0];i++){

		int v=g[u][i];

		if(!f[v]&&!tag[u][v]){

			f[v]=1;

			if(!match[v]||hungarian(match[v],flag)){

				if(flag) match[v]=u;

				return 1;

			}

		}

	}

	return 0;

}

int main(){

	int T=0;

	while(~scanf("%d%d%d",&n,&m,&k)){

		T++;

	memset(dt,0,sizeof(dt));

	memset(g,0,sizeof(g));

	memset(match,0,sizeof(match));

	memset(bj,0,sizeof(bj));

	for(int i=1;i<=k;i++){

		int x=init(),y=init();

		dt[x][y]=1;

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(dt[i][j]) g[i][++g[i][0]]=j;

		}

	}

	int ans=0;

	for(int i=1;i<=n;i++){

		memset(f,0,sizeof(f));

		if(hungarian(i,1)) ans++;

	}

	int cnt=0;

	for(int i=1;i<=m;i++) if(match[i]) bj[match[i]]=1;

	for(int i=1;i<=m;i++){

		if(match[i]){

		tag[match[i]][i]=1;

		int t=match[i];bj[t]=0;

		match[i]=0;

		bool fff=0;

		for(int j=1;j<=n;j++){

			memset(f,0,sizeof(f));

			if(!bj[j]&&hungarian(j,0)) {fff=1;break;}

		}

		if(fff) cnt++;

		match[i]=t;bj[t]=1;

		tag[match[i]][i]=0;}

	}

	printf("Board %d have %d important blanks for %d chessmen.\n",T,ans-cnt,ans);

	}

	return 0;

}