二分图 poj 1486 匹配是否唯一_判断二分图匹配是否唯一-CSDN博客

本文链接：https://blog.csdn.net/Yonggie/article/details/77186111

本文介绍了一个用于寻找唯一匹配的问题解决方案，通过构建图模型并利用最大匹配算法来确定哪些匹配是唯一的。文章详细解释了实现过程，包括如何进行输入处理、构建匹配关系、使用匈牙利算法查找最大匹配以及如何验证每个匹配的唯一性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

这个题啊……一开始竟然读错题意了5555

人家说把能够唯一确定的所有匹配给输出出来，而不是整体的匹配唯一才输出。

也就是说，你可能一共有6个文件6个标志，但是唯一确定的匹配有4个，还有两个不能确定，这样你要输出4个而不是输出none……

哎……不是wa在方法上而是wa在细节上啊、

方法：

先求一边最大匹配，然后暴力枚举删掉每一个匹配到的边，然后在求最大匹配，如果最大匹配数和原来没删边的数量相等那么这个匹配就不唯一，就不要输出，如果结果不一样，那么这个匹配就是唯一的，就要输出。

AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;

struct paper
{
    int xmin,xmax,ymin,ymax;
}pa[maxn];
struct mark
{
    int x,y;
}ma[maxn];

int N;
bool used[maxn];
bool mp[maxn][maxn];

bool check(mark mar,paper pap)
{
    if(mar.x<pap.xmax&&mar.x>pap.xmin&&mar.y<pap.ymax&&mar.y>pap.ymin)
        return 1;
    return 0;
}
int mate[maxn];//纸张为i的标号是谁。
int path[maxn];

bool Findm(int x)// paper number
{
    for(int i=1;i<=N;i++)
    {
        if(!used[i]&&mp[x][i])
        {
            used[i]=1;
            if(!mate[i]||Findm(mate[i]))
            {
                mate[i]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int cas=1;
    while(scanf("%d",&N)==1&&N)
    {
        //input graph.
        memset(mp,0,sizeof(mp));
        for(int i=1;i<=N;i++)
            scanf("%d%d%d%d",&pa[i].xmin,&pa[i].xmax,&pa[i].ymin,&pa[i].ymax);

        for(int i=1;i<=N;i++)
            scanf("%d%d",&ma[i].x,&ma[i].y);

        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=N;j++)
            {
                if(check(ma[i],pa[j]))
                    mp[i][j]=1;
            }
        }

        //initialize the mate array.
       int have=0;
       memset(mate,0,sizeof(mate));
       for(int i=1;i<=N;i++)//mark number.
       {
           memset(used,0,sizeof(used));
           have+=Findm(i);
       }

        //judging
        for(int i=1;i<=N;i++) path[i]=mate[i];

        bool f=0;
        printf("Heap %d\n",cas++);
        for(int i=1;i<=have;i++)
        {
            int cnt=1;
            int temp=0;
            mp[path[i]][i]=0;
            memset(mate,0,sizeof(mate));
            for(int j=1;j<=N;j++)
            {
                memset(used,0,sizeof(used));
                temp+=Findm(j);
            }

            if(temp==have) continue;//this edge is not unique.
            else
            {
                if(f) printf(" ");
                f=1;
                printf("(%c,%d)",i-1+'A',path[i]);
            }
            mp[path[i]][i]=1;
        }

        if(!f) printf("none");
        printf("\n\n");
    }
}