BZOJ.3495.[PA2010]Riddle(2-SAT 前缀优化建图)

题目链接

每个城市要么建首都要么不建，考虑2-SAT

这样一个国家内城市两两连边是很显然的，但是边数为O(n^2)

每个国家中仅有一个建首都，考虑新建前缀S[i]=1/0这2n个点表示当前国家的[1,i]中建了/没建首都

现在考虑这些限制:(A[i]=1/0表示i城市建/不建)

0.若A[i]=1，则S[i]=1；若S[i]=0，则A[i]=0(对于i自己)

1.若A[i]=1，则S[i-1]=0；若S[i-1]=1，则A[i]=0 (一个国家一个首都的限制)(前者由A[i]->A[i-1]'是多余的，连到\(S_{i-1}'\)自然会连到\(A_{i-1}'\))

2.若S[i-1]=1，则S[i]=1；若S[i]=0，则S[i-1]=0 (前缀关系)

后缀优化的原理是一样的，不过这题并不需要

再加上边端点的限制就可以了

//167004kb	16344ms

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=4e6+5,M=N<<1;

int n,m,k,Enum,H[N],nxt[M],to[M],id,low[N],dfn[N],sk[N],top,cnt,bel[N];

bool ins[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline void AddEdge(int u,int v){

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;

}

inline void Tarjan(int x)

{

	dfn[x]=low[x]=++id, ins[x]=1, sk[++top]=x;

	for(int v,i=H[x]; i; i=nxt[i])

		if(!dfn[v=to[i]]) Tarjan(v),low[x]=std::min(low[x],low[v]);

		else if(ins[v]) low[x]=std::min(low[x],dfn[v]);

	if(low[x]==dfn[x])

	{

		++cnt;

		do{

			ins[sk[top]]=0, bel[sk[top]]=cnt;

		}while(x!=sk[top--]);

	}

}

int main()

{

	n=read(),m=read(),k=read();

	for(int u,v,i=1; i<=m; ++i)

		u=read(),v=read(),AddEdge(u+n,v),AddEdge(v+n,u);

	for(int i=1; i<=n; ++i) AddEdge(i,2*n+i),AddEdge(3*n+i,i+n);

	for(int num,now,las,i=1; i<=k; ++i)

	{

		num=read(), las=read();

		for(int j=2; j<=num; ++j,las=now)

		{

			now=read(),

			AddEdge(2*n+las,2*n+now), AddEdge(3*n+now,3*n+las),

			AddEdge(now,3*n+las), AddEdge(2*n+las,now+n);

		}

	}

	for(int i=1; i<=n<<2; ++i)

		if(!dfn[i]) Tarjan(i);

	for(int i=1; i<=n; ++i)

		if(bel[i]==bel[i+n]) {printf("NIE"); return 0;}

	for(int i=n<<1|1; i<=3*n; ++i)

		if(bel[i]==bel[i+n]) {printf("NIE"); return 0;}

	printf("TAK");

	return 0;

}

//150832kb	19404ms

//{//优化编号方式 注意这样编号要-1 -> 于是这样更慢了...?

//	for(int u,v,i=1; i<=m; ++i)

//		u=read()-1,v=read()-1,AddEdge(u<<1|1,v<<1),AddEdge(v<<1|1,u<<1);

//	for(int i=0; i<n; ++i) AddEdge(i<<1,i+n<<1),AddEdge(i+n<<1|1,i<<1|1);

//	for(int num,now,las,i=1; i<=k; ++i)

//	{

//		num=read(), las=read()-1;

//		for(int j=2; j<=num; las=now,++j)

//		{

//			now=read()-1,

//			AddEdge(las+n<<1,now+n<<1), AddEdge(now+n<<1|1,las+n<<1|1),

//			AddEdge(now<<1,las+n<<1|1), AddEdge(las+n<<1,now<<1|1);

//		}

//	}

//	n<<=2;

//	for(int i=0; i<n; ++i)

//		if(!dfn[i]) Tarjan(i);

//	for(int i=0; i<n; i+=2)

//		if(bel[i]==bel[i^1]) {printf("NIE"); return 0;}

//	printf("TAK");

//}

巴特西

BZOJ.3495.[PA2010]Riddle(2-SAT 前缀优化建图)

最新文章

热门文章