P5782 [POI2001] 和平委员会 题解

P5782 [POI2001] 和平委员会

题目传送门

题意

一共有(2n)个人，第(2i-1)和(2i)个人为一组((1le i le n))，给出(m)组矛盾关系((x,y))，表示第(x)和第(y)个人不能同时选，问有没有每组都选出一个人的方案，如果有就随便输出一种方案

题解

看到题目中矛盾关系，又要求我们构造方案，很容易想到 (2-SAT)
我们考虑怎么进行连边
根据 (2-SAT) 的思路，只有明确选择关系的才能进行连边
于是思路就有了，我们直接将矛盾关系的两个人各自与对方同一组的另一个人进行连边，因为选了这个人之后与他有矛盾关系的人就不能选了，所以只能选择同组的另一个人，如图（假设(A1)和(B1)矛盾）：

然后就可以愉快地套板子了

CODE

#include<cstdio>
#include<string>
#define R register int
#define N 8005
#define M 20005
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
struct arr{int to,nxt;}e[M<<2];
int n,m,head[N<<1],dfn[N<<1],low[N<<1],stack[N<<1],top,cnt,tot,db[N<<1],scc[N<<1];
bool bz[N<<1];
int max(int a,int b) {return a>b?a:b;}
int min(int a,int b) {return a<b?a:b;}
void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
void add(int u,int v)
{
	e[++cnt].to=v;e[cnt].nxt=head[u];
	head[u]=cnt;
}
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;stack[++top]=u;bz[u]=1;
	for (R i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if (bz[v]) low[u]=min(low[u],dfn[v]);
	}
	if (low[u]==dfn[u])
	{
		++tot;
		while (stack[top]!=u)
		{
			scc[stack[top]]=tot;bz[stack[top--]]=0;
		}
		scc[stack[top]]=tot;bz[stack[top--]]=0;
	}
}
int main()
{
	read(n);n<<=1;read(m);
	for (R i=1;i<=n;++i)
		if (i&1) db[i]=i+1;else db[i]=i-1;
	for (R x,y,i=1;i<=m;++i)
	{
		read(x);read(y);
		add(x,db[y]);add(y,db[x]);
	}
	cnt=0;
	for (R i=1;i<=n;++i)
		if (!dfn[i]) tarjan(i);
	for (R i=1;i<=n;i+=2)
		if (scc[i]==scc[i+1]) {printf("NIE
");return 0;}
	for (R i=1;i<=n;i+=2)
		if (scc[i]<scc[i+1]) printf("%d
",i);else printf("%d
",i+1);
	printf("
");
 	return 0;
}