POJ – 1486 – Sorting Slides (二分匹配的唯一边)

2017年11月21日 0 条评论 11 次阅读 0 人点赞

题目链接:POJ - 2594 

题目大意:

故纸堆:桌上有n张幻灯片杂乱地叠在一起,给出每张幻灯片的边界和页码坐标,求在不翻动的情况下哪些页码可以确定?

页码可能在保护页码坐标的任意一张幻灯片上

题目分析:

二分图找唯一匹配的边,即删除该边之后无法形成完美匹配。

首先见图找到一个完美匹配。逐个删除完美匹配中的其中一条边,再进行二分图匹配看是否形成完美匹配,如果不能,则该边是唯一边。

给出代码:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1000+10;
int g[maxn][maxn];
int link[maxn];
int vist[maxn];
int mark[maxn];
struct node
{
int minx;
int miny;
int maxx;
int maxy;
}nodes[maxn];
int n;
int v1,v2;
bool dfs(int x)
{
for(int i=0;i<v2;i++)
{
if(!vist[i]&&g[x][i])
{
vist[i]=1;
if(link[i]==-1||dfs(link[i]))
{
link[i]=x;
return true;
}
}
}
return false;
}
int research()
{
    int ans=0;
memset(link,-1,sizeof(link));
for(int i=0;i<v1;i++)
{
memset(vist,0,sizeof(vist));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
    int kase=0;
   	while(cin>>n&&n)
{
        memset(g,0,sizeof(g));
for(int i=0;i<n;i++)
{
cin>>nodes[i].minx>>nodes[i].maxx>>nodes[i].miny>>nodes[i].maxy;
}
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
for(int j=0;j<n;j++)
{
if(x>=nodes[j].minx&&x<=nodes[j].maxx&&y>=nodes[j].miny&&y<=nodes[j].maxy)
{
g[i][j]=1;
}
}
}
v1=v2=n;
cout<<"Heap "<<++kase<<endl;
int ans=research();
if(ans<n)
cout<<"none"<<endl;
else
{
int flag=1;
for(int i=0;i<n;i++)
{
mark[i]=link[i];
}
for(int i=0;i<n;i++)
{
g][i]=0;
if(research()==n)
{
       // g[link[i]][i]=1;
continue;
}
else
{
if(!flag)
cout<<" ";
else
flag=0;
printf("(%c,%d)",(char)(i+'A'),mark[i]+1);
g][i]=1;
}
}
if(flag)
cout<<"none";
cout<<endl;
}
cout<<endl;
}
return 0;
//system("pause");
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)