POJ1486 Sorting Slides 二分图最大匹配 必要匹配

本文主要是介绍POJ1486 Sorting Slides 二分图最大匹配 必要匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题意：读题读得很纠结~~

大意就是平面坐标上有一系列的矩形（各边都和坐标轴平行）和

一些点；每个矩形和在他之内的点对应；

然后找出那些绝对匹配（就是在任何最大匹配中，某个矩形和某个点始终对应）；

所谓必要匹配在本题中的意思就是，在所有的最大匹配中，1个数字都会匹配到同一个字母上去。数字x只能与字母y匹配才是最大匹配的话x，y就是必要匹配了

使用的方法就是先做一次最大匹配，然后对每个数字，将其匹配的边删掉后的图中进行寻找增广路的操作，如果能找到增广，看能否跟其他点匹配。说明该数字的匹配不唯一。

否则就输出。

另外本题最好用邻接矩阵来做，因为数字比较小并且删边时操作方便。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 30;
const int inf = 1<<29;
int nx,ny;
bool map[maxn][maxn],vis[maxn];
int dist,cx[maxn],cy[maxn],dx[maxn],dy[maxn],dis[maxn];
struct node
{int x1,x2,y1,y2;
}slide [maxn];bool dfs( int u )
{for( int v = 1; v <= ny; v ++ ){if( map[u][v] && !vis[v] ){vis[v] = true;if( cy[v] == -1 || dfs( cy[v] ) ){cy[v] = u;return true;}}}return false;
}int MaxMatch()
{int ans = 0;memset(cy,-1,sizeof(cy));for( int i = 1; i <= nx; i ++ ){memset(vis,0,sizeof(vis));ans += dfs(i);}return ans;
}void getMust()
{int flag = 0;for( int i = 1; i <= nx; i ++ ){int temp = cy[i];cy[i] = -1;map[temp][i] = false;memset(vis,0,sizeof(vis));if( !dfs(temp) ){if( flag ) printf(" ");printf("(%c,%d)",'A'+i-1,temp );cy[i] = temp;flag = 1;}map[temp][i] = true;}if( !flag )printf("none\n");elseprintf("\n");
}int main()
{//freopen("data.txt","r",stdin);int n,x,y,cas = 0;while( scanf("%d",&n) != EOF,n ){nx = ny = n;for( int i = 1; i <= n; i ++ ){scanf("%d%d%d%d",&slide[i].x1,&slide[i].x2,&slide[i].y1,&slide[i].y2 );}for( int i = 1; i <= n; i ++ ){scanf("%d%d",&x,&y);for( int j = 1; j <= n; j ++ ){if( x > slide[j].x1 && x < slide[j].x2 && y > slide[j].y1 && y < slide[j].y2 )map[i][j] = 1;elsemap[i][j] = 0;}}MaxMatch();if( cas )	puts("");printf("Heap %d\n",++cas);getMust();}return 0;
}

这篇关于POJ1486 Sorting Slides 二分图最大匹配 必要匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---