【xsy1648】最小点覆盖 二分图最小点覆盖

题目 网络流

---

题意

  最小点覆盖是指在二分图中，用最小的点集覆盖所有的边。当然，一个二分图的最小点覆盖可能有很多种。

  现在给定一个二分图，请你把图中的点分成三个集合：
  如果在任何一种最小点覆盖中都不包含这个点，则认为该点属于 $N$ 集合。
  如果在任何一种最小点覆盖中都包含这个点，则认为该点属于 $A$ 集合。
  如果一个点既不属于 $N$ 集合，又不属于 $A$ 集合，则认为该点属于 $E$ 集合。

   $1\le n,m\le 1000$

分析

  首先我们有 Konig定理 ：

$$最小点覆盖数=最大匹配数$$
  证明：
   ① 构造： 从左边未匹配的点开始，找交错轨，将所有的点标记。取左边所有未标记的点，和右边所有标记的点。
   ② 证明构造出来的点集大小恰好为最大匹配数
   ③ 证明构造出来的点集是点覆盖集
   ④ 证明点覆盖集的大小取到最小

  根据上面点覆盖集的理论，差不多就可以做这一道题了。
  我们先跑出一个匹配。一个不在任意一个匹配上的点，一定不在点覆盖集中。因为我们从这个点可以跑出若干条交错轨，交错轨的点数为奇数，且左边的点比右边的点多一个，所以一定选左边的点。
  由于一种匹配方案对应一种点覆盖集的构造方案，一条匹配边有且仅有一个点在点覆盖集上，所以与不在匹配上的点相邻的一定是点覆盖集中的点。
  也正是因为如此，与一定在点覆盖集中的点匹配的点一定不再点覆盖集中。
  我们BFS一次就好了，没有遍历到的点就可能在，可能不在了。

实现

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
const int N=2005;
const int E=2000005;
int n,m,k;
struct Ed {
    int v,nx;
    inline Ed(int _v=0,int _nx=0):v(_v),nx(_nx){}
}mp[E];
int tot,hd[N];
int v[N];
int mat[N];
int col[N];
namespace input {
    const int SIZE=2000000;
    char buffer[SIZE];
    char *head=buffer+SIZE;
    char *tail=head;
    inline char getchr(void) {
        if (head==tail) {
            fread(buffer,1,SIZE,stdin);
            head=buffer;
        }
        return *head++;
    }
    inline int rd(void) {
        int x=0,f=1; char c=getchr();
        for (;!isdigit(c);c=getchr()) if (c=='-') f=-1;
        for (;isdigit(c);c=getchr()) x=x*10+c-'0';
        return x*f;
    }
}
using input::rd;
inline void Ins(int u,int v) {
    mp[++tot]=Ed(v,hd[u]); hd[u]=tot;
    mp[++tot]=Ed(u,hd[v]); hd[v]=tot;
}
int Hungary(int x) {
    for (int k=hd[x];k>0;k=mp[k].nx)
        if (!v[mp[k].v]) {
            v[mp[k].v]=1;
            if (!mat[mp[k].v]||Hungary(mat[mp[k].v])) {
                mat[mp[k].v]=x;
                mat[x]=mp[k].v;
                return 1;
            }
        }
    return 0;
}
void BFS(void) {
    static int q[N]; int qh=0,qt=0;
    F(i,1,n+m)
        if (!mat[i]) {
            col[i]=1;
            q[++qt]=i;
        }
    while (qh!=qt) {
        int x=q[++qh];
        if (col[x]==1) {
            for (int k=hd[x];k>0;k=mp[k].nx)
                if (!col[mp[k].v]) {
                    col[mp[k].v]=2;
                    q[++qt]=mp[k].v;
                }
        }
        else if (col[x]==2) {
            if (mat[x]>0&&!col[mat[x]]) {
                col[mat[x]]=1;
                q[++qt]=mat[x];
            }
        }
    }
}
void Print(void) {
    static char s[N];
    F(i,1,n)
        if (!col[i]) s[i]='E';
        else if (col[i]==1) s[i]='N';
        else if (col[i]==2) s[i]='A';
    s[n+1]=0;
    printf("%s\n",s+1);
    F(i,n+1,n+m)
        if (!col[i]) s[i-n]='E';
        else if (col[i]==1) s[i-n]='N';
        else if (col[i]==2) s[i-n]='A';
    s[m+1]=0;
    printf("%s\n",s+1);
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    cin>>n>>m>>k;
    F(i,1,k) {
        int x=rd(),y=rd();
        Ins(x,n+y);
    }
    F(i,1,n+m) if (!mat[i]) {
        memset(v,0,sizeof v);
        Hungary(i);
    }
    memset(col,0,sizeof col);
    BFS();
    Print();
    return 0;
}