UOJ210寻找罪犯

UOJ210

\(2-sat\)问题

这算前后缀优化嘛（？）感觉不算啊

设置\(2*n\)个节点表示某个人是不是劫匪

再设置\(2*m\)个节点表示第\(i\)句话以及之前有没有说过谎

具体连边在注释里说叭

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
#define y1 qwq 
	inline int read()
	{
		int x=0;char ch,f=1;
		for(ch=getchar();(ch<‘0‘||ch>‘9‘)&&ch!=‘-‘;ch=getchar());
		if(ch==‘-‘) f=0,ch=getchar();
		while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();}
		return f?x:-x;
	}
	const int N=3e6+10,inf=1<<30;
	int n,m,num;
	int pre[N],ans[N];
	int head[N],cnt;
	struct point
	{
		int nxt,to;
		point(){}
		point(const int &nxt,const int &to):nxt(nxt),to(to){}
	}a[N<<1];
	inline void link(int x,int y)
	{
		a[++cnt]=(point){head[x],y};head[x]=cnt;
	}
	inline int check(int a,int b){return a+b*n;}
	inline int work(int a,int b){return (n<<1)+a+b*m;}
	int dfn[N],low[N],st[N],col[N];
	int idx,top,sum;
	inline void tarjan(int now)
	{
		dfn[now]=low[now]=++idx;
		st[++top]=now;
		for(int i=head[now];i;i=a[i].nxt)
		{
			int t=a[i].to;
			if(!dfn[t])
			{
				tarjan(t);
				low[now]=min(low[now],low[t]);
			}
			else if(!col[t]) low[now]=min(low[now],dfn[t]);
		}
		if(dfn[now]==low[now])
		{
			col[now]=++sum;
			while(st[top]!=now) col[st[top--]]=sum;
			--top;
		}
	}
	inline void main()
	{
		n=read(),m=read();
		for(int i=1;i<=n;++i) pre[i]=2*m+1;
		for(int x,y,opt,i=1;i<=m;++i)
		{
			x=read(),y=read(),opt=read()^1;
			link(check(y,opt^1),work(pre[x],0));
			//这句话是假话，以前都是真话 
			link(work(pre[x],1),check(y,opt));
			//上句话是假话，这句话是真话 
			link(work(i,0),check(y,opt));
			//这句话以及之前都是真话 
			link(check(y,opt^1),work(i,1));
			//这句话是假话，这句话以及以前有假话 
			link(work(i,0),work(pre[x],0));
			//这句话以及以前都是真话，这句话以前都是真话 
			link(work(pre[x],1),work(i,1));
			// 这句话以前有假话，这句话以及以前有假话 
			pre[x]=i;
		}
		for(int i=1;i<=n;++i)
		{
			link(work(pre[i],1),check(i,1));
			//这个人说过假话，这个人死啦死啦滴 
			link(check(i,0),work(pre[i],0));
			//这个人很诚实，是个好人 
		}
		for(int i=1;i<=(n+m)<<1;++i)
			if(!dfn[i]) tarjan(i);
		for(int i=1;i<=n;++i)
		{
			if(col[i]==col[i+n])
			{
				puts("Impossible");
				return;
			}
			else if(col[i]>col[i+n]) ans[++num]=i;
		}
		printf("%d\n",num);
		for(int i=1;i<=num;++i) printf("%d ",ans[i]);
	}
}
signed main()
{
	//freopen("haha.in","r",stdin);
	red::main();
	return 0;
}

UOJ210寻找罪犯

原文：https://www.cnblogs.com/knife-rose/p/12700973.html