HDU1281(最大二分匹配+枚举)

求能放最多的车，就是求最大二分匹配。判断是不是重要点，只需把出去这个点，走一遍最大匹配，看结果是不是一样，如果一样，则不是重要点，然后枚举每个点即可。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define maxn 1005
#define INF 999999999
using namespace std;

int f[maxn][maxn];
int vis[maxn];
int flag[maxn];
int n,m,k;
int u[maxn],v[maxn];

bool DFS(int a)
{
	for(int i=1;i<=m;i++)
	{
		if(f[a][i] && !vis[i])
		{
			vis[i]=1;
			if(flag[i]==0 || DFS(flag[i]))
			{
				flag[i]=a;
				return true;
			}
		}
	}
	return false;
}

void init()
{
	memset(f,0,sizeof(f));
	memset(flag,0,sizeof(flag));
}

int main()
{
	int cont=1;
	while(scanf("%d%d%d",&n,&m,&k)!=EOF)
	{
		init();
		for(int i=1;i<=k;i++)
		{
			scanf("%d%d",&u[i],&v[i]);
			f[u[i]][v[i]]=1;
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			memset(vis,0,sizeof(vis));
			if(DFS(i))
				ans++;
		}
		int num=0;
		for(int i=1;i<=k;i++)
		{
			f[u[i]][v[i]]=0;
			memset(flag,0,sizeof(flag));
			int temp=0;
			for(int j=1;j<=n;j++)
			{
				memset(vis,0,sizeof(vis));
				if(DFS(j))
					temp++;
			}
			if(temp!=ans)
				num++;
			f[u[i]][v[i]]=1;
		}
		printf("Board %d have %d important blanks for %d chessmen.\n",cont++,num,ans);
	}
	return 0;
}

HDU1281(最大二分匹配+枚举),布布扣,bubuko.com

HDU1281(最大二分匹配+枚举)

原文：http://blog.csdn.net/mfmy_szw/article/details/23124565