学步园

点击打开链接

Konig定理：二分图的最小顶点覆盖数 = 二分图的最大匹配数

题意： 在N*N的网络中有K颗小行星。小行星i的位置是(Ri, Ci)。现在有一个强力的武器能够用一发光束将一整行或一整列的小行星消灭。想要利用这个武器消灭所有的小行星最少需要几发光束？

分析： 以小行星的左右坐标建立二分图，就可以看出是求二分图的最小顶点覆盖数。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 500 + 5; //单侧顶点的最大数目

struct BPM{
    int n, m; //左右顶点个数
    vector<int> G[maxn];  //邻接表
    int left[maxn];//left[i]为右边第i个点的匹配点编号，-1表示不存在
    bool T[maxn];//T[i]为右边第i个点是否已标记

    int right[maxn]; //求最小覆盖用
    bool S[maxn];    //求最小覆盖用

    void init(int n, int m){
        this->n = n;
        this->m = m;
        for(int i=0; i<n; ++i) G[i].clear();
    }

    void AddEdge(int u, int v){
        G[u].push_back(v);
    }

    bool match(int u){
        S[u] = true;
        for(int i=0; i<G[u].size(); ++i){
            int v = G[u][i];
            if(!T[v]){
                T[v] = true;
                if(left[v]==-1 || match(left[v])){
                    left[v] = u;
                    right[u] = v;
                    return true;
                }
            }
        }
        return false;
    }

    //求最大匹配
    int solve()
    {
        memset(left, -1, sizeof left );
        memset(right, -1, sizeof right );
        int ans = 0;
        for(int u=0; u<n; ++u){
            //从左边结点u开始增广
            memset(S, 0, sizeof S );
            memset(T, 0, sizeof T );
            if(match(u)) ans++;
        }
        return ans;
    }
    //求最小覆盖。 X 和 Y为最小覆盖中的点集
    int mincover(vector<int>& X, vector<int>& Y){
        int ans = solve();
        memset(S, 0, sizeof S );
        for(int u =0; u<n; ++u)
            if(right[u]==-1) match(u);
            //从所有X未盖点出发增广
        for(int u=0; u<n; ++u)
            if(!S[u]) X.push_back(u); //X中的未标记点
        for(int v=0; v<m; ++v)
            if(T[v]) Y.push_back(v); //Y中的已标记点
        return ans;
    }
};

BPM  solver;
int main()
{
    int i, j, n, k;
    scanf("%d%d", &n, &k);
    solver.init(n, n);
    for(i=0; i<k; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x--; y--;
        solver.AddEdge(x, y);  //有向图
    }
    int ans = solver.solve();
    printf("%d\n", ans);
    return 0;
}