【POJ】3648 Wedding

时间：2022-02-10 08:09:08

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

题意：n对人（编号0～n-1，'w'表示第一个人，'h'表示第二个人），每对两个，人坐在桌子两侧。满足：1、每对人中的两个人不能坐在同一侧。2、m对关系x和y，表示x和y不能坐在同一侧，但是能坐在第0对的第一个人的那一侧。问第0对的第一个人那一侧坐着的人。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

using namespace std;

const int N=1005;

int tot, FF[N], LL[N], p[N], in[N], num, all, top, ok[N], vis[N], pos[N], n, m;

struct Gr {

	int ihead[N], cnt;

	struct E{ int next, to; }e[N*N<<2];

	Gr() { cnt=0; memset(ihead, 0, sizeof ihead); }

	void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }

	void tarjan(int x) {

		static int s[N];

		FF[x]=LL[x]=++tot; vis[x]=1; s[++top]=x;

		for(int i=ihead[x]; i; i=e[i].next)

			if(!FF[e[i].to]) tarjan(e[i].to), LL[x]=min(LL[x], LL[e[i].to]);

			else if(vis[e[i].to]) LL[x]=min(LL[x], FF[e[i].to]);

		if(FF[x]==LL[x]) {

			int y; ++num;

			do { y=s[top--]; vis[y]=0; p[y]=num; } while(x!=y);

		}

	}

	void tarjan() { tot=0; top=0; num=0; for(int i=0; i<all; ++i) if(!FF[i]) tarjan(i); }

	void rebuild(Gr &g) {

		for(int x=0; x<all; ++x)

			for(int i=ihead[x]; i; i=e[i].next) if(p[x]!=p[e[i].to])

				in[p[x]]++, g.add(p[e[i].to], p[x]);

		for(int x=0; x<all; x+=2) pos[p[x]]=p[x|1], pos[p[x|1]]=p[x];

	}

	void topo() {

		static int q[N], front, tail; front=tail=0;

		for(int i=0; i<num; ++i) if(!in[i]) q[tail++]=i;

		while(front!=tail) {

			int x=q[front++];

			if(!ok[x]) ok[x]=1, ok[pos[x]]=2;

			for(int i=ihead[x]; i; i=e[i].next) if(!(--in[e[i].to])) q[tail++]=e[i].to;

		}

	}

	void clr() {

		memset(ihead, 0, sizeof(int)*(all));

		cnt=0;

	}

}g, G;

void clr() {

	memset(FF, 0, sizeof(int)*(all));

	memset(in, 0, sizeof(int)*(all));

	memset(ok, 0, sizeof(int)*(all));

	memset(p, 0, sizeof(int)*(all));

	memset(pos, 0, sizeof(int)*(all));

	G.clr(); g.clr();

	all=0;

}

bool work() {

	all=n<<1;

	g.tarjan();

	for(int i=0; i<all; i+=2) if(p[i]==p[i+1]) return 0;

	g.rebuild(G);

	G.topo();

	int white=ok[p[0]]; // printf("%d\n", white);

	for(int i=1; i<n-1; ++i) printf("%d%c ", i, white==ok[p[i<<1]]?'w':'h');

	printf("%d%c\n", n-1, white==ok[p[(n-1)<<1]]?'w':'h');

	return 1;

}

int main() {

	while(scanf("%d%d", &n, &m), !(n==0&&m==0)) {

		for(int i=0; i<m; ++i) {

			static char s1, s2;

			int x, y;

			scanf("%d%c%d%c", &x, &s1, &y, &s2);

			int a=x<<1|(s1=='h'),

				b=y<<1|(s2=='h');

			g.add(a, b^1); g.add(b, a^1);

		}

		g.add(0, 1);

		if(!work()) puts("bad luck");

		clr();

	}

	return 0;

}

　　

一开始写的好几个都给wa了= =因为感觉整个题我写得都有问题，所以一怒之下我删了！然后看别人家的代码= =（但是后来发现本题有一个坑，就是读入的时候可能没有空格，因此不能读入"%s%s"= =，会不会这样就能a掉了呢= =）

这题我做得很郁闷= =各种不想说了..

大家请转移阵地（请结合三份题解一起看= =感觉各有缺漏= =）= =http://www.cnblogs.com/staginner/archive/2011/10/02/2198263.html，http://www.cnblogs.com/kuangbin/archive/2012/10/05/2712429.html，http://blog.csdn.net/qq172108805/article/details/7603351

（这里我不得不说一下= =状态设的是第0对第一个人的“对面”= =大家千万不要搞错了= =

那么 x -> y'的意思表示x坐在对面那么y'一定也坐在对面

最后0w -> 0h表示0对人只有h人坐在对面。

相关文章