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