Poj 1486 Sorting Slides + FOJ1202 信与信封问题 (二分图的必须边)

淩亂°似流年 2021-11-23 05:16 150阅读 0赞

2015-4-27更新：由于百度空间即将关闭，故将提到的参考文章复制到了最下面。

理论：http://hi.baidu.com/wrpnjmkfhgbimpq/item/e8402237ef272afbdf222100

步骤：

1：求最大匹配，匹配边集合E

2：删除E中的一条边e，以e的一个端点找增广路，若不能找到增广路则e是必须边

3：恢复原图以及E，继续步骤2，直到E中的每条边都被删除过

**Poj 1486 Sorting Slides**

题意：一些重叠在一起的图片，给你这些图片的四个坐标，给出一些写在图片上的数字的坐标，找到一个匹配使得每一个数字都可以唯一对应于一张图片

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    const int N=40;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int n;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=n;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==0 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    struct Rectangle
    {
    	int xmin,xmax,ymin,ymax;
    	void Get ()
    	{
    		scanf("%d%d%d%d",&xmin,&xmax,&ymin,&ymax);
    	}
    }r[N];
    
    struct Point
    {
    	int x,y;
    	void Get ()
    	{
    		scanf("%d%d",&x,&y);
    	}
    }p[N];
    
    bool Judge (Rectangle a,Point b)
    {
    	if (b.x>=a.xmin && b.x<=a.xmax && b.y>=a.ymin && b.y<=a.ymax)
    		return true;
    	return false;
    }
    
    void Deal ()
    {
    	int i,sum=0,flag=0;
    	for (i=1;i<=n;i++)
    	{
    		memset(vis,false,sizeof(vis));
    		if (Dfs(i))
    			sum++;
    	}
    	if (sum==n)
    	{
    		for (i=1;i<=n;i++)
    		{
    			int u=match[i];
    			if (u==0)
    				continue;
    			match[i]=0;
    			map[u][i]=false;
    			memset(vis,false,sizeof(vis));
    			if (Dfs(u)==false)
    			{
    				flag++;
    				match[i]=u;
    				if (flag>1)
    					printf(" ");
    				printf("(%c,%d)",i-1+'A',match[i]);
    			}
    			map[u][i]=true;
    		}
    	}
    	if (flag==0)
    		printf("none");
    	printf("\n");
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int Cas=1;
    	while (~scanf("%d",&n),n)
    	{
    		if (Cas!=1)
    			printf("\n");
    		printf("Heap %d\n",Cas++);
    		memset(map,false,sizeof(map));
    		memset(match,0,sizeof(match));
    		int i;
    		for (i=1;i<=n;i++)
    			r[i].Get();
    		for (i=1;i<=n;i++)
    			p[i].Get();
    		for (i=1;i<=n;i++)   //建图
    			for (int j=1;j<=n;j++)
    			{
    				if (Judge(r[i],p[j]))
    					map[j][i]=true;  //有向边方向与match数组方向对应
    			}
    		Deal ();
    	}
    	return 0;
    }

**FOJ1202 信与信封问题**

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const int N=105;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int n;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=n;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==0 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    
    struct Point
    {
    	int x,y;
    	bool operator < (const Point& b) const
    	{
    		return x<b.x;
    	}
    }data[N];
    
    void Deal ()
    {
    	int i,sum=0,flag=0;
    	for (i=1;i<=n;i++)
    	{
    		memset(vis,false,sizeof(vis));
    		if (Dfs(i))
    			sum++;
    	}
    	if (sum==n)
    	{
    		for (i=1;i<=n;i++)
    		{
    			int u=match[i];
    			if (u==0)
    				continue;
    			match[i]=0;
    			map[u][i]=false;
    			memset(vis,false,sizeof(vis));
    			if (Dfs(u)==false)
    			{
    				match[i]=u;
    				data[flag].x=match[i];
    				data[flag++].y=i;			
    			}
    			map[u][i]=true;
    		}
    	}
    	if (flag==0)
    		printf("none\n");
    	else
    	{
    		sort(data,data+flag);
    		for (i=0;i<flag;i++)
    			printf("%d %d\n",data[i].x,data[i].y);
    	}
    	printf("\n");
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	while (~scanf("%d",&n))
    	{
    		memset(map,true,sizeof(map));
    		memset(match,0,sizeof(match));
    		int a,b;
    		while (scanf("%d%d",&a,&b),a||b)
    		{
    			map[a][b]=false;
    		}
    		Deal ();
    	}
    	return 0;
    }

## 二分图的必须边: POJ1486, FOJ1202 ##

在自己做的二分图的题目当中，除了常见的最大匹配、最小覆盖、最大独立集、最小路径覆盖、带权最佳匹配外，自己还发现一类题型，就是要求出二分图里的哪些边是能够确定的。因为自己没系统的学习过二分图，我暂时把这些边叫做二分图的必须边。这些题的一般是给出哪些边可能存在或一定不存在，要你通过计算输出这样的二分图中哪些边是一定存在的。

先看一个例子:POJ1486

这道题的意思是一些大小不等透明的幻灯片（只有轮廓和上面的数字可见）A、B、C、D、E…按顺序叠放在一起，现在知道每个幻灯片左上角和右下角的坐标，并且由于幻灯片是透明的，所以能看到幻灯片上的数字（给出了每个数字的坐标，但不知道这些数字分别属于哪个幻灯片），现在要你根据当前的已知信息，输出能够确定的幻灯片编号和数字的匹配，例如(A,4) (B,1) (C,2) (D,3).

解这道题的思路是：先根据已知信息建立二分图，通过坐标计算把可能存在的边赋值为1，然后用匈牙利算法进行最大匹配，当前则得到了一个最大匹配，然后每次删除一条边，对该边的一个顶点进行再次匹配，如果匹配成功则不是必须边，只有匹配不成功才是必须边。

核心代码大致如下：

MaxMatch(); //进行最大匹配

yes = 0;

for(i = 1; i <= n; i++) //验证match\[i\]与i是不是唯一匹配的

x = match\[i\]; match\[i\] = -1;

g\[x\]\[i\] = 0;

memset(flag, 0, sizeof(flag));

if(!dfs(x))//如果dfs(x)==0即找不到,就表示是唯一匹配，即可输出！

match\[i\] = x;

yes++;

if(yes > 1) printf(" ");