POJ 3041 Asteroids (最小点覆盖集)

题意

给出一个N*N的矩阵，有些格子上有障碍，要求每次消除一行或者一列的障碍，最少消除多少次可以全部清除障碍。

思路

把关键点取出来：一个障碍至少需要被它的行或者列中的一个消除。 也许是最近在做二分图匹配专辑吧……很容易想到这就是 最小点覆盖集：每条边都至少需要一个点被选中，称这条边被覆盖。 而由 König定理可知 二分图最小点覆盖 = 最大匹配。所以解法也就出来了： 把行当作左点集，列当作右点集，对于每一个障碍，把它的行和列对应的点连一条边，此二分图的最大匹配就是答案了。

代码

 

using namespace std;
const int MAXV = 1005;                   //N1+N2
vector  adj[MAXV];
struct MaximumMatchingOfBipartiteGraph{
    int vn;
    void init(int n){                   //二分图两点集点的个数
        vn = n;
        for (int i = 0; i <= vn; i ++)     adj[i].clear();
    }
    void add_uedge(int u, int v){
		adj[u].push_back(v);
		adj[v].push_back(u);
    }
    bool vis[MAXV];
    int mat[MAXV];                      //记录已匹配点的对应点
    bool cross_path(int u){
        for (int i = 0; i < (int)adj[u].size(); i ++){
            int v = adj[u][i];
            if (!vis[v]){
                vis[v] = true;
                if (mat[v] == 0 || cross_path(mat[v])){
                    mat[v] = u;
                    mat[u] = v;
                    return true;
                }
            }
        }
        return false;
    }
    int hungary(){
        mem(mat, 0);
        int match_num = 0;
        for (int i = 1; i <= vn; i ++){
            mem(vis, 0);
            if (!mat[i] && cross_path(i)){
                match_num ++;
            }
        }
        return match_num;
    }
}match;

int main(){
	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);
    int n, k;
    while(scanf("%d %d", &n, &k) != EOF){
        match.init(2*n);
        for (int i = 0; i < k; i ++){
            int r, c;
            scanf("%d %d", &r, &c);
            match.add_uedge(r, c+n);
        }
        printf("%d\n", match.hungary());
    }
	return 0;
}