幻灯片 / Sorting Slides

题目链接：ybt金牌导航3-1-5 / luogu UVA663 / POJ 1486

题目大意

有些幻灯片，每个幻灯片会在随机在它的其中一个位置有一个编号。
幻灯片会放在一起，而编号都浮现在最上面，可能导致分不清哪个编号对应哪个幻灯片。
你要求出那些能够得出对应关系的幻灯片和编号。

思路

首先很明显你能求出一个编号在哪些幻灯片中。

那它其实就是要把编号和幻灯片配对，直接上二分图，网络流来搞。

但是你会发现它要求的不是配对的个数，而是现在能配对确定的配对。
（注意这里就算没有全部配对好也要求出可以确定的配对输出，是完全什么都不能确定才输出 none）

那要怎么搞呢?
它要能确定配对，一是有配对的方法，二是这个配对的方法是唯一的。
那简单，如果对于每个配对，我们把它配对用的边在二分图中删去，然后重新跑最大匹配。
如果新的匹配数量比之前少了，那一定是之前能配对的现在不能跟其他配对，那就说明这个配对方法是唯一的，那这个配对方法就可以被输出。

然后这题挺烦的，它的输出格式比较约束，最好不要有行末空格，回车符的个数一个数据之后是放两个回车。
而且我因为每次跑 dinic 都是用同一个函数，你不删边跑出来的一些值要存出来，不然因为后面的 dinic 改了就锅了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f 

using namespace std;

struct node {
	int xx, x, to, nxt, op;
}e[10001];
int n, x1[61], y1[61], x2[61], y2[61], real_gogo[4001];
int x, y, le[4001], lee[4001], S, T, ans, befans;
int cnt, dis[4001], gogo[4001], KK, line_[4001], real_line_[4001];
queue <int> q;

void csh() {
	KK = 0;
	memset(le, 0, sizeof(le));
	memset(gogo, 0, sizeof(gogo));
	memset(line_, 0, sizeof(line_));
}

bool ck(int i, int j, int k) {
	if (i < x1[k] || i > x2[k]) return 0;
	if (j < y1[k] || j > y2[k]) return 0;
	return 1;
}

void add(int x, int y, int z) {
	e[++KK] = (node){z, z, y, le[x], KK + 1}; le[x] = KK;
	e[++KK] = (node){0, 0, x, le[y], KK - 1}; le[y] = KK;
}

bool bfs(int cannot) {
	while (!q.empty()) q.pop();
	for (int i = 1; i <= T; i++) {
		dis[i] = -1;
		lee[i] = le[i];
	}
	
	q.push(S);
	dis[S] = 0;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		for (int i = le[now]; i; i = e[i].nxt)//前两个判断就是表示不走那条边（下面 dfs 也一样）
			if (i != cannot && e[i].op != cannot && e[i].x > 0 && dis[e[i].to] == -1) {
				dis[e[i].to] = dis[now] + 1;
				if (e[i].to == T) return 1;
				q.push(e[i].to);
			}
	}
	
	return 0;
}

int dfs(int now, int sum, int cannot) {
	if (now == T) return sum;
	
	int go = 0;
	for (int &i = lee[now]; i; i = e[i].nxt)
		if (i != cannot && e[i].op != cannot && e[i].x > 0 && dis[e[i].to] == dis[now] + 1) {
			int this_go = dfs(e[i].to, min(sum - go, e[i].x), cannot);
			if (this_go) {
				if (now >= 1 && now <= n && e[i].to >= n + 1 && e[i].to <= 2 * n)
					gogo[e[i].to] = now, line_[now] = i;
				e[i].x -= this_go;
				e[e[i].op].x += this_go;
				go += this_go;
				if (go == sum) return go;
			}
		}
	
	if (go < sum) dis[now] = -1;
	return go;
}

void dinic(int cannnot) {
	while (bfs(cannnot))
		ans += dfs(S, INF, cannnot);
}

bool check(int i) {
	for (int j = 1; j <= KK; j++)//记得图要还原到没有流过的时候
		e[j].x = e[j].xx;
	ans = 0;
	dinic(real_line_[i]);
	if (ans == befans - 1) return 1;//有影响说明是唯一配对方案
	return 0;//否则不是
}

int main() {
//	freopen("read.txt", "r", stdin);
	
	scanf("%d", &n);
	while (n) {
		csh();
		
		for (int i = 1; i <= n; i++) {
			scanf("%d %d %d %d", &x1[i], &x2[i], &y1[i], &y2[i]);
		}
		
		for (int i = 1; i <= n; i++) {
			scanf("%d %d", &x, &y);
			for (int j = 1; j <= n; j++)
				if (ck(x, y, j)) add(i, j + n, 1); 
		}
		
		S = 2 * n + 1;
		T = 2 * n + 2;
		for (int i = 1; i <= n; i++) {
			add(S, i, 1);
			add(i + n, T, 1);
		}
		
		ans = 0;
		dinic(0);
		befans = ans;
		
		printf("Heap %d\n", ++cnt);
		for (int i = 1 + n; i <= 2 * n; i++)//你不删边时跑的记录流向的位置和流的边都要记下来，它可能会因为后面的跑的删边 dinic 而改变
			real_gogo[i] = gogo[i];
		for (int i = 1; i <= n; i++)
			real_line_[i] = line_[i];
		
		bool have_ans = 0, first = 1;
		for (int i = 1; i <= n; i++) {
			if (check(real_gogo[i + n])) {//把对应的边删了看是否有影响
				if (first) first = 0;
					else printf(" ");
				printf("(%c,%d)", i + 'A' - 1, real_gogo[i + n]);
				have_ans = 1;
			}
		}
		if (!have_ans) printf("none");
		
		printf("\n\n");
		
		scanf("%d", &n);
	}
	
	return 0;
}