POJ 3041

题意

• 给出nxn的图有m个行星(点).弹药每次能消灭一行或一列上的所有行星(点).问最少需要几次能消灭所有的行星(点)?

思路

• 将样例数据横坐标x作为二分图左部分的一个点.纵坐标y作为二分图右部分的一个点.坐标(x,y)表示为二分图左部分的x点到右部分的y点的边.画出这样的一个二分图:

1. 求消灭所有行星也就是 画出来的二分图的所有点需要被覆盖.
2. 每次消灭一行或一列 等价于 从二分图取一个点且边所连接的点也被覆盖.
3. 例如取左边点2 等价于 消灭第二行 (同理 取右边点3 等价于 消灭第3列),
4. 那么该点的边连接到的点也被覆盖.问题转化为取最少的点 将 二分图覆盖 (二分图的最小覆盖)

---

• 理解了上面. 那么弹药(消灭某行或某列) = 二分图某一点, 原图的点 代表 二分图中的边

二分图最小覆盖 = 最大匹配

• 最后求最大匹配就行了 (理解至上)
• 很好的证明 博客

#include <iostream>
#include <cstring>

using namespace std;
const int maxn = 505;
int g[maxn][maxn],match[maxn];
bool vis[maxn];
int n,m;

int dfs(int u) {
    for (int j=1; j<=n; ++j) {
        if (g[u][j] && !vis[j]) {
            vis[j] = 1;
            if (!match[j] | dfs(match[j])) {
                match[j] = u;
                return 1;
            }
        }
    }
    return 0;
}
void init() {
    memset(match,0,sizeof match);
    memset(g,0,sizeof g);
}
int main() {
    freopen("1.in","r",stdin);
    while (scanf("%d%d",&n,&m) != EOF) {
        init();
        while (m--) {
            int x,y;
            scanf("%d%d",&x,&y);
            g[x][y] = 1;
        }
        int res = 0;
        for (int i=1; i<=n; ++i) {
            memset(vis,0,sizeof vis);
            if (dfs(i)) ++res;
        }
        printf("%d\n",res);
    }
    return 0;
}