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

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

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

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

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

#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"); 
    }
}

/*
 题意描述：输入幻灯片的坐标位置，页码的坐标位置，将能唯一确定页码的幻灯片按照顺序输出，
 如果没有一张能够唯一确定则输出none
 */
 /*
 解题思路：基本思路是将幻灯片和页码进行匹配，按照二分图匹配的思路求最大匹配，如果某一条边
 是唯一边，则将这条边去掉以后，该二分图的最大匹配数将<n,输出该匹配边。
 */
 #include<stdio.h>
 #include<string.h>
 const int N=;
 struct Slide{
     int xmin,xmax,ymin,ymax;
 }slide[N];
 struct Num{
     int x,y;
 }num[N];
 int n,e[N][N],cx[N],cy[N],bk[N];
 int maxmatch();
 int path(int u);
 
 int main()
 {
     int i,j,t=;
     while(scanf("%d",&n), n != )
     {
         for(i=;i<n;i++)
             scanf("%d%d%d%d",&slide[i].xmin,&slide[i].xmax,&slide[i].ymin,&slide[i].ymax);
         for(i=;i<n;i++)
             scanf("%d%d",&num[i].x,&num[i].y);
 
         memset(e,,sizeof(e));
         for(i=;i<n;i++){
             for(j=;j<n;j++){
                 if(num[i].x>slide[j].xmin && num[i].x<slide[j].xmax
                 && num[i].y>slide[j].ymin && num[i].y<slide[j].ymax)
                 e[j][i]=;//点i在j张里，按照输出顺序，先输出字母，再输出数字
             }
         }    
 
         printf("Heap %d\n",++t);
         int flag=;
         for(i=;i<n;i++){
             for(j=;j<n;j++){
                 if(e[i][j])
                 {
                     e[i][j]=;
                     if(maxmatch() < n)
                     {
                         if(flag)
                         printf(" (%c,%d)",'A'+i,j+);
                         else
                         printf("(%c,%d)",'A'+i,j+);
                         flag=;
                     }
                     e[i][j]=;
                 }
             }
         }
 
         if(flag)
         printf("\n\n");
         else
         printf("none\n\n");
     }
     return ;
 }
 
 int maxmatch()
 {
     int i;
     memset(cx,-,sizeof(cx));
     memset(cy,-,sizeof(cy));
     int ans=;
     for(i=;i<n;i++)
     {
         if(cy[i]==-)
         {
             memset(bk,,sizeof(bk));
             ans += path(i);
         }
     }
     return ans;
 }
 int path(int u)
 {
     int i;
     for(i=;i<n;i++)
     {
         if(e[u][i] && !bk[i])
         {
             bk[i]=;
             if(cx[i]==- || path(cx[i]))
             {
                 cx[i]=u;
                 cy[u]=i;
                 return ;
             }
         }
     }
     return ;
 }
 /*易错分析：按照输出顺序，先幻灯片再页码，所以输入边的时候j在前，i在后*/