【ybt金牌導航3-6-2】【luogu UVA11294】【POJ 3648】婚禮 / Wedding

婚禮 / Wedding

題目連結：ybt金牌導航3-6-2 / luogu UVA11294 / POJ 3648

題目大意

有一堆夫婦，然後有兩邊，同一對夫婦不能在同一邊。

同時再給出一些條件，就是不能讓某兩個人同時在左邊。

問你是否有成立的情況，然後如果有，輸出其中一種合法的方案。

思路

首先，你看到題目，自然會想到用 2-set 來做。

然後你考慮建邊，對于每一對，有男的在新郎旁邊和女的在新郎旁邊。

然後如果有沖突，就互相連到互相的另一半。

然後這裡有個關鍵的點就是新娘要連一條邊到新郎。

為什麼呢？

那你想，隻有新郎是有限制的，新娘這邊就是随便坐。

那我們 2-set 肯定要讓電腦找的是新郎的這邊啊。

那怎麼弄呢？我們就可以這樣連邊，這樣如果選了新娘就一定要選新郎，就會出現錯誤。但如果徐娜了新郎就不會有鍋。

然後我們來看看怎麼找答案 。

2-set 找答案是利用拓撲序，然後還是逆拓撲序，因為按逆的就不會産生沖突，不用逆的有可能會跟前面已經排好的産生沖突。

然後你會發現逆拓撲序其實就是你縮點的順序，那就不用再跑一遍求了。

然後怎麼通過逆拓撲序看放那邊呢？

因為你 2-set 選的是新郎的，答案是要新娘的，我們隻要到時反過來即可。

然後現在說的是新郎那邊的。

那如果對于某一對，那它兩個點會各有逆拓撲序。那你肯定是先處理逆拓撲序前的，也就是拓撲序後的，那就選這個點所對應的。

（記得在這道題要反過來！！！）

然後就可以了。

代碼

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

struct node {
	int to, nxt;
}e[500010];
int n, m, x, y, le[5001], KK;
char cx, cy, answer[5001];
int dfn[5001], low[5001], tmp;
int sta[5001], in[5001], n_n;
bool cant;

void csh() {//初始化
	memset(e, 0, sizeof(e));
	memset(le, 0, sizeof(le));
	KK = 0;
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	tmp = 0;
	memset(sta, 0, sizeof(sta));
	memset(in, 0, sizeof(in));
	n_n = 0;
	cant = 0;
}

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

int another(int x) {
	if (x > n) return x - n;
	return x + n;
}

void tarjan(int now) {//Tarjan縮點
	dfn[now] = low[now] = ++tmp;
	sta[++sta[0]] = now;
	
	for (int i = le[now]; i; i = e[i].nxt)
		if (!dfn[e[i].to]) {
			tarjan(e[i].to);
			low[now] = min(low[now], low[e[i].to]);
		}
		else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);
	
	if (dfn[now] == low[now]) {
		in[now] = ++n_n;
		while (sta[sta[0]] != now) {
			in[sta[sta[0]]] = n_n;
			sta[0]--;
		}
		sta[0]--;
	}
	
	return ;
}

int main() {
	scanf("%d %d", &n, &m);
	while (n || m) {
		csh();
		
		for (int i = 1; i <= m; i++) {
			scanf("%d%c %d%c", &x, &cx, &y, &cy);
			x++;
			y++;
			if (cx == 'h') x += n;
			if (cy == 'h') y += n; 
			add(x, another(y));//建圖
			add(y, another(x));
		}
		add(1, 1 + n);//讓程式選新郎那邊的，因為新娘那邊沒有限制
		
		for (int i = 1; i <= 2 * n; i++)
			if (!dfn[i]) tarjan(i);
		
		for (int i = 1; i <= n; i++)//2-sat 的判斷沖突
			if (in[i] == in[n + i]) {
				cant = 1;
				printf("bad luck\n");
				break;
			}
		if (cant) {
			scanf("%d %d", &n, &m);
			continue;
		}
		
		for (int i = 2; i <= n; i++) {
			printf("%d", i - 1);//根據拓撲排序
			if (in[i] > in[i + n]) printf("w");
				else printf("h");
			printf(" ");
		}
		printf("\n");
		
		scanf("%d %d", &n, &m);
	}
	
	return 0;
}