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;
}




全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务