在线性时间内寻找二分图的唯一匹配

Question

在O(m+n)内寻找到二分图的唯一匹配

输入:
n: 顶点的数量
m: 顶点之间边的数量
Li: 左侧顶点的数组，每个数组中的元素是一个邻接链表。邻接链表中是该顶点所连接的右边的顶点。
Rj: 右侧顶点的数组，每个数组中的元素是一个邻接链表。邻接链表中是该顶点所连接的左边的顶点。

输出:
M: 如果二分图存在一个唯一的映射，就返回该映射，否则返回None。如果二分图存在部分唯一匹配，则返回None.

如图左边的二分图就可以确定一个唯一匹配，该算法就需要返回该唯一的匹配。右边的二分图就无法确认唯一匹配，该算法返回None。
左侧顶点的数量和右侧顶点数量是一样的。

Answer 1

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=55;

inline int read()
{
    char ch=getchar();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
    return i*f; 
} 

int n,T,x1[Maxn],x2[Maxn],y1[Maxn],y2[Maxn];
int before[Maxn*Maxn*2],to[Maxn*Maxn*2],last[Maxn*2],ecnt,mate[Maxn*2],vis[Maxn*2],vt,ban[Maxn*Maxn*2];

inline void add(int x,int y)
{
    before[++ecnt]=last[x];
    last[x]=ecnt;
    to[ecnt]=y;
}

inline bool Hungary(int i)
{
    for(int e=last[i];e;e=before[e])
    {
        if(ban[e]||vis[to[e]]==vt)continue;
        vis[to[e]]=vt;
        if(!mate[to[e]]||Hungary(to[mate[to[e]]]))return mate[i]=e,mate[to[e]]=e^1,true;
    }
    return false;
}

int main()
{
    while(n=read(),n)
    {
        T++;ecnt=1;vt=0;
        memset(last,0,sizeof(last));memset(mate,0,sizeof(mate));memset(vis,0,sizeof(vis));memset(ban,0,sizeof(ban));
        for(int i=1;i<=n;i++)x1[i]=read(),x2[i]=read(),y1[i]=read(),y2[i]=read();
        for(int i=1;i<=n;i++)
        {
            int x=read(),y=read();
            for(int j=1;j<=n;j++)
            {
                if(x>=x1[j]&&x<=x2[j]&&y>=y1[j]&&y<=y2[j])add(i+n,j),add(j,i+n);
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(mate[i]){continue;}
            vt++;Hungary(i);
        }
        printf("Heap %d\n",T);
        for(int i=1;i<=n;i++)
        {
            int t1=mate[i],t2=t1^1;
            ban[t1]=ban[t2]=1;
            mate[i]=mate[to[t1]]=0;
            ++vt;
            if(Hungary(i))cnt++;
            else
            {
                mate[i]=t1,mate[to[t1]]=t2;
                printf("(%c,%d) ",'A'+i-1,to[mate[i]]-n);
            }
            ban[t1]=ban[t2]=0;
        }
        if(cnt==n)printf("None");
        printf("\n\n"); 
    }
}