学步园

Air Raid  http://poj.org/problem?id=1422
    题目是要求最大独立子集，而最大独立子集是最小覆盖集互为补集
    由konig定理，二分图的最小顶点覆盖数等于最大匹配数

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 508;
int G[N][N],link[N],used[N],n,m;

bool path(int u)
{
	for(int i=0;i<m;i++)
		if(G[u][i] && !used[i])
			{
				used[i] = 1;
				if(link[i]==-1 || path(link[i]))
				{
					link[i] = u;
					return true;
				}			
			}
	return false;
}

void  hungary()
{
	int i,ans = 0;
	memset(link,-1,sizeof(link));
	for(i=0;i<n;i++)
	{
		memset(used,0,sizeof(used));
		if(path(i)) ans++;
	}
	cout<<n-ans<<endl;  //最大独立子集和最小覆盖集(ans)互为补集 , 
}

int main()
{
	int c,i,j,k,a,b;
	scanf("%d",&c);
	while(c--)
	{
		scanf("%d%d",&m,&k);
		memset(G,0,sizeof(G));
		n=m;
		for(i=0;i<k;i++)
		{
			scanf("%d%d",&a,&b);
			G[a-1][b-1] = 1;
		}
		hungary();	
	}
	return 0;
}