poj 1422 Air Raid(最小パスオーバーライド+二分図最大マッチング)

http://poj.org/problem?id=1422
題意:有向無環図では、いくつかの頂点から図上のすべての点を遍歴することができ、初期に選択された頂点数が最も少なく、頂点が重複しないことが要求される.
考え方:
ある頂点からループするプロセスがパスの選択と見なされる場合、問題は、図中のすべての頂点を上書きする最小の交差したくない単純なパスをループ図の有無に変換する.最小パスオーバーライドに関する問題が表示されます.
有向無ループ図では、最小パスオーバーライド数 = 「ノード数」(Node Count)-二分図に対応する最大一致数.
最小パスオーバーライドは、元の図が有向無環図である必要があります.次に、原図に基づいて二分図を構築する方法は、原図中の各頂点viを二つに分け、vi*とvi**に対応し、原図にviからvjまでの有向エッジが存在する場合、頂点vi*とvj**の間に無方向エッジが接続され、パスカバー問題に対応する二分図が構築され、この二分図に基づいて最大マッチング数が求められる.

#include 
#include 
#include 
using namespace std;

const int maxn = 130;
int n,m;
bool map[maxn][maxn];
int match[maxn];
int chk[maxn];

bool dfs(int p)
{
	for(int i = 1; i <= n; i++)
	{
		if(map[p][i] && !chk[i])
		{
			chk[i] = 1;
			if(match[i] == -1 || dfs(match[i]))
			{
				match[i] = p;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int test;
	int x,y;
	scanf("%d",&test);
	while(test--)
	{
		memset(map,false,sizeof(map));
		scanf("%d %d",&n,&m);
		for(int i = 0; i < m; i++)
		{
			scanf("%d %d",&x,&y);
			map[x][y] = true;		//     
		}

		memset(match,-1,sizeof(match));
		int res = 0;

		for(int i = 1; i <= n; i++)
		{
			memset(chk,0,sizeof(chk));
			if(dfs(i)) res += 1;
		}
		printf("%d
",n-res);
	}
	return 0;
}