POJ 1486 Sorting Slides(二分图最大匹配:关键边)

POJ 1486 Sorting Slides(二分图最大匹配:关键边)

http://poj.org/problem?id=1486

题意:

一些幻灯片,有一些数字在幻灯片里面,看能不能使得一个数字只能对应一张幻灯片.第一行代表有几张幻灯片.

给出这几张幻灯片的坐标,接着n行代表1-n个数字对应的坐标,然后要求你打印一个确定的使一个数字对应一张幻灯片.

如果不能对应输出none.

存在某些幻灯片只能由某个数字代表的话就按字典序打印出这些幻灯片和对应的数字.

分析:

其实就是二分图最大匹配问题.左边点集用幻灯片编号表示,右边点集用数字表示. 如果某个幻灯片i包含了数字j,那么从左边i到右边j就存在一条边.

首先我们求出这个图的最大匹配数x, 根据题意这x值一定是等于n(幻灯片数的). 然后我们记录目前求到的最大匹配的各个边.

我们每次判断最大匹配边集的某条边是否是必需边. 我们只要先删除这条边,如果之后求最大匹配数依然==n,那么这条边不是必需边.如果之后求最大匹配数依然<n,那么这条边是必需边.(做好标记)

最终我们只需要输出所有的必须边即可.

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=26+5;

struct Max_Match
{
    int n,m;
    bool g[maxn][maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n)
    {
        this->n=n;
        memset(g,0,sizeof(g));
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int v=1;v<=n;v++)if(g[u][v] && !vis[v])
        {
            vis[v]=true;
            if(left[v]==-1 || match(left[v]))
            {
                left[v]=u;
                return true;
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ans++;
        }
        return ans;
    }
}MM;

int xmin[maxn],ymin[maxn],xmax[maxn],ymax[maxn];
struct
{
    int x;  // edge[i].x=x 表示第i个矩形配对的数字 是x;
    bool ok;//标记该边是否是 必需边
}edge[maxn];

int main()
{
    int n,kase=0;
    while(scanf("%d",&n)==1&&n)
    {
        MM.init(n);
        memset(edge,0,sizeof(edge));
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&xmin[i],&xmax[i],&ymin[i],&ymax[i]);
        }
        for(int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            for(int j=1;j<=n;j++)
            {
                if(xmin[j]<=x&&x<=xmax[j]&&ymin[j]<=y&&y<=ymax[j])
                    MM.g[j][i]=true;
            }
        }
        MM.solve();
        int edge_num=n;
        for(int i=1;i<=n;i++)
        {
            edge[MM.left[i]].x=i;
            edge[MM.left[i]].ok=true;
        }
        for(int i=1;i<=n;i++)//尝试删除第i条匹配边
        {
            int j=edge[i].x;
            MM.g[i][j]=false;//删除此边
            memset(MM.left,-1,sizeof(MM.left));
            int num = MM.solve();
            if(num == n)//删除边后,匹配数不变
            {
                edge[i].ok=false;
                edge_num--;
            }
            MM.g[i][j]=true;//还原此边
        }
        printf("Heap %d\n",++kase);
        if(edge_num==0) printf("none\n");
        else
        {
            for(int i=1;i<=n;i++)if(edge[i].ok)
                printf("(%c,%d) ",i-1+'A',edge[i].x);
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}