POJ1486 Sorting Slides 二分图

Sorting Slides 二分图"/>

POJ1486 Sorting Slides 二分图

  这题的意思是给你N张幻灯片，然后有一些点，每个点都有编号，如果点在幻灯片中，则两者存在边，要求存在唯一的完美匹配，并输出它，否则输出none，在这题中，先建立边，然后求最大匹配，并删边，如果删边了求匹配还是N，则证明此匹配不唯一，若不是，便可以输出。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define maxn 1005
#define mem(a) memset(a, 0, sizeof(a))
using namespace std;bool map[maxn][maxn], vis[maxn];
int lk[maxn], tmppoint[maxn], n;struct slid
{int xmin, xmax, ymin, ymax;
}sl[maxn];bool jug(int x, int y, int a)
{if(x >= sl[a].xmin&&x <= sl[a].xmax&&y >= sl[a].ymin&&y <= sl[a].ymax)return true;return false;	
}bool dfs(int a)
{int i;for(i = 0;i < n;i++){if(!vis[i]&&map[a][i]){vis[i] = 1;if(lk[i] == -1||dfs(lk[i])){lk[i] = a;return true;}}}return false;
}int res()
{int i, ress = 0;memset(lk, -1, sizeof(lk));for(i = 0;i < n;i++){mem(vis);if(dfs(i))ress++;}return ress;
}int main(int argc, char *argv[])
{int xmin, xmax, ymin, ymax, px, py, i, j, eagenum, o = 0, flag;while(scanf("%d", &n)&&n){mem(map);mem(sl);mem(tmppoint);for(i = 0;i < n;i++){scanf("%d%d%d%d", &sl[i].xmin, &sl[i].xmax, &sl[i].ymin, &sl[i].ymax);}for(i = 0;i < n;i++){scanf("%d%d", &px, &py);for(j = 0;j < n;j++){if(jug(px, py, j))map[i][j] = 1;}}eagenum = res();flag = 0;printf("Heap %d\n", ++o);if(eagenum == n){for(i = 0;i < n;i++)tmppoint[i] = lk[i];for(i = 0;i < n;i++){map[tmppoint[i]][i] = 0;if(res() == n)continue;else{if(flag)printf(" ");printf("(%c,%d)", i + 'A', tmppoint[i] + 1);flag = 1;}map[tmppoint[i]][i] = 1;}}if(!flag)printf("none");printf("\n\n");}return 0;
}