训练指南 UVA - 11419（二分图最小覆盖数）

时间：2023-12-16 15:10:14

layout: post

title: 训练指南 UVA - 11419（二分图最小覆盖数）

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 二分图

- 最小点覆盖

- 图论

- 训练指南

SAM I AM

UVA - 11419

题目大意：给出一个R×C的网格，网格上棉纺了一些目标。可以在网格外发射子弹，子弹会沿着垂直或水平方向飞行，并且打掉飞行路径上的所有目标。你的任务是计算出最少需要多少子弹，各从哪个位置发射，才能把所有目标全部打掉。

解题思路：König定理：最小覆盖数等于最大匹配数。把目标所在的坐标，转化为XY结点，行看成X结点，列看成Y结点。那现在问题就变成了，如何选最少的结点，覆盖所有的边。

求最小覆盖的步骤大致如下：1）在右边找到一个未被匹配过的点，标记。2）走一条没被匹配过的边，到左边的点，标记。3）走一条匹配过的边到右边，标记。4）重复2,3步骤直到不能再走。5）回到步骤一，直到找不到未被匹配且未被标记的右边的点。6）标记结束后，右边没有标记的点，和左边标记过的点，就可以覆盖所有的边。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e3+50;

const ll inf=1e10;

const ll INF = 1000000000;

const double eps=1e-5;

#define bug cout<<"bbibibibbbb="<<endl;

/// 二分图最大基数匹配

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++){

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

        memset(T,0,sizeof(T));

        for(int u=0;u<n;u++)

            if(right[u]==-1)match(u);

        for(int u=0;u<n;u++)

            if(!S[u])X.push_back(u);

        for(int v=0;v<n;v++)

            if(T[v])Y.push_back(v);

        return ans;

    }

};

BPM solver;

int R,C,N;

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int kase=0;

    while(cin>>R>>C>>N&&R&&C&&N){

        solver.init(R,C);

        for(int i=0;i<N;i++){

            int r,c;

            cin>>r>>c;r--;c--;

            solver.AddEdge(r,c);

        }

        vector<int>X,Y;

        int ans=solver.mincover(X,Y);

        cout<<ans;

        for(int i=0;i<X.size();i++)cout<<" r"<<X[i]+1;

        for(int j=0;j<Y.size();j++)cout<<" c"<<Y[j]+1;

        cout<<endl;

    }

    return 0;

}

相关文章