UVa 663 & POJ 1486 Sorting Slides

想法：
    做最大匹配，做完可從llink[i]=j得到每條匹配的邊(i,j)，也就是(i,j)是可能的答案，但要確認這條邊(i,j)的唯一性。
    例如Sample Input的第二個測資，做完最大匹配可得到(A,1)(B,2)兩條邊，最大匹配數為2，要確認(A,1)是否唯一，就把(A,1)這條邊去掉並且禁止，然後再做一次最大匹配，會變成得到(A,2)(B,1)，最大匹配數還是2，與數量原來一樣並沒有減少，因此可知(A,1)這條邊不唯一。同理(B,2)也把它去掉並禁止，再做一次最大匹配，如果最大匹配數比原本小，這條邊就是答案可以輸出，反之如果最大匹配數和原本一樣，則這條邊不唯一不能輸出。
    從底下code可以看到最大匹配的模板函數Bipartite(int n, int u, int v)多了兩個參數u, v，表示做最大匹配的時候禁止(u,v)這條邊的使用(line 65)。

UVa版：

	#include <cstdio>
	#include <cstring>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> toNxt[1000];
	int llink[1000], rlink[1000];
	bool used[1000];
	int Bipartite(int n, int u, int v);
	bool dfs(int now, int u, int v);
	int main()
	{
	int n, Case = 1;
	int Xmin[1000], Xmax[1000], Ymin[1000], Ymax[1000];
	int X, Y;
	while (scanf("%d", &n) && n) {
	for (auto &v : toNxt) v.clear();
	// Input
	for (int i = 0; i < n; ++i)
	scanf("%d %d %d %d", &Xmin[i], &Xmax[i], &Ymin[i], &Ymax[i]);
	for (int i = 0; i < n; ++i) {
	scanf("%d %d", &X, &Y);
	for (int j = 0; j < n; ++j)
	if (Xmin[j]<=X && X<=Xmax[j] && Ymin[j]<=Y && Y<=Ymax[j])
	toNxt[j].push_back(i);
	}
	// Bipartite
	int result = Bipartite(n, -1, -1);
	int ans[1000];
	for (int i = 0; i < n; ++i) ans[i] = llink[i];
	// Analysis & Output
	printf("Heap %d\n", Case++);
	bool ok = false;
	for (int i = 0; i < n; ++i) {
	if (Bipartite(n, i, ans[i]) < result) {
	if (ok) putchar(' ');
	printf("(%c,%d)", (i+'A'), ans[i]+1);
	ok = true;
	}
	}
	if (ok == false) printf("none");
	printf("\n\n");
	}
	}
	int Bipartite(int n, int u, int v)
	{
	fill(llink, llink+n, -1);
	fill(rlink, rlink+n, -1);
	int num = 0;
	for (int i = 0; i < n; ++i) {
	fill(used, used + n, false);
	if (dfs(i, u, v)) ++num;
	}
	return num;
	}
	bool dfs(int now, int u, int v)
	{
	for (int nxt : toNxt[now]) {
	if (used[nxt] || (now==u && nxt==v)) continue;
	used[nxt] = true;
	if (rlink[nxt] == -1 || dfs(rlink[nxt], u, v) == true) {
	llink[now] = nxt;
	rlink[nxt] = now;
	return true;
	}
	}
	return false;
	}

view raw [UVa] 663 Sorting Slides.cpp hosted with ❤ by GitHub

POJ版：

	#include <cstdio>
	#include <cstring>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> toNxt[1000];
	int llink[1000], rlink[1000];
	bool used[1000];
	int Bipartite(int n, int u, int v);
	bool dfs(int now, int u, int v);
	int main()
	{
	int n, Case = 1;
	int Xmin[1000], Xmax[1000], Ymin[1000], Ymax[1000];
	int X, Y;
	while (scanf("%d", &n) && n) {
	for (int i = 0; i < n; ++i)
	toNxt[i].clear();
	// Input
	for (int i = 0; i < n; ++i)
	scanf("%d %d %d %d", &Xmin[i], &Xmax[i], &Ymin[i], &Ymax[i]);
	for (int i = 0; i < n; ++i) {
	scanf("%d %d", &X, &Y);
	for (int j = 0; j < n; ++j)
	if (Xmin[j]<=X && X<=Xmax[j] && Ymin[j]<=Y && Y<=Ymax[j])
	toNxt[j].push_back(i);
	}
	// Bipartite
	int result = Bipartite(n, -1, -1);
	int ans[1000];
	for (int i = 0; i < n; ++i) ans[i] = llink[i];
	// Analysis & Output
	printf("Heap %d\n", Case++);
	bool ok = false;
	for (int i = 0; i < n; ++i) {
	if (Bipartite(n, i, ans[i]) < result) {
	if (ok) putchar(' ');
	printf("(%c,%d)", (i+'A'), ans[i]+1);
	ok = true;
	}
	}
	if (ok == false) printf("none");
	printf("\n\n");
	}
	}
	int Bipartite(int n, int u, int v)
	{
	fill(llink, llink+n, -1);
	fill(rlink, rlink + n, -1);
	int num = 0;
	for (int i = 0; i < n; ++i) {
	fill(used, used + n, false);
	if (dfs(i, u, v)) ++num;
	}
	return num;
	}
	bool dfs(int now, int u, int v)
	{
	for (int i = 0; i < toNxt[now].size(); ++i) {
	int nxt = toNxt[now][i];
	if (used[nxt] || (now==u && nxt==v)) continue;
	used[nxt] = true;
	if (rlink[nxt] == -1 || dfs(rlink[nxt], u, v) == true) {
	llink[now] = nxt;
	rlink[nxt] = now;
	return true;
	}
	}
	return false;
	}

view raw [POJ] 1486 Sorting Slides.cpp hosted with ❤ by GitHub