POJ 3041 Asteroids 匈牙利算法 二分图最大匹配

题目链接：http://poj.org/problem?id=3041

看起来像个 DP 神马的。竟然是二分图匹配。。

看着啊，行与行之间相互独立，一个行可以就炸掉很多列。（列的道理一样），如果替换一些字。

               点与点之间相互独立，一个点就可以炸掉很多边。

so，可以把行列看成一个点，把一个炸弹看成一条边，然后题目就转换城了最小点击覆盖（即最大匹配）。

尼玛，鬼能想到这样的思路。。。

这个题的思路就是上面说的，每一个炸弹（x，y）看做一条边，两个端点就是它的行列x 和 y。任意炸掉x y期中一个点都可以把可以把这条边炸掉。跟题目一样了。

就这么神奇。。

代码：

#include <cstdio>
#include <cstring>

const int N = 555;
int n, m, g[N][N], chk[N], match[N];

int dfs(int v){
	int t;
	for ( int i = 1; i <= n; i++){
		if ( g[i][v] && !chk[i] ){
			chk[i] = 1;
			t = match[i];
			match[i] = v;
			if ( t == -1 || dfs(t) ) return 1;
			match[i] = t;
		}
	}
	return 0;
}

int main(){
	while ( ~scanf("%d%d", &n ,&m) ){
		memset(g, 0, sizeof(g));
		while ( m-- ){
			int a, b;
			scanf("%d%d", &a, &b);
			g[a][b] = 1;
		}
		int ans = 0;
		memset(match, 255, sizeof(match));
		for ( int i = 1; i <= n; i++){
			memset( chk, 0, sizeof(chk));
			ans += dfs(i);
		}
		printf("%d\n", ans);
	}
	return 0;
}