正题

题目链接:https://www.luogu.com.cn/problem/P6378

题目大意

给出\(n\)个点\(m\)条边的一张无向图，图中有\(k\)种颜色的点。

要求每种颜色选择一个点作为关键点，满足每条边两边至少有一个关键点

求是否有满足的方案

\(1\leq n,m,k\leq 10^6\)

解题思路

如果想到\(2-SAT\)的话就挺好解决的了。

然后一个经典的问题是一堆点里面选了一个点就不能选其他点。

可以考虑优化建图，搞一些前缀点和一些后缀点就好了

时间复杂度\(O(n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<stack>

using namespace std;

const int N=5e6+10;

struct node{

	int to,next;

}a[N<<1];

int n,m,k,cnt,tot,dfc,cfc;

int ls[N],dfn[N],low[N],col[N];

bool ins[N];vector<int> v[N];

stack<int> s;

void addl(int x,int y){

	a[++tot].to=y;

	a[tot].next=ls[x];

	ls[x]=tot;return;

}

void tarjan(int x){

	dfn[x]=low[x]=++dfc;

	s.push(x);ins[x]=1;

	for(int i=ls[x];i;i=a[i].next){

		int y=a[i].to;

		if(!dfn[y]){

			tarjan(y);

			low[x]=min(low[x],low[y]);

		}

		else if(ins[y])

			low[x]=min(low[x],dfn[y]);

	}

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

		++cfc;

		while(s.top()!=x){

			col[s.top()]=cfc;

			ins[s.top()]=0;

			s.pop();

		}

		col[s.top()]=cfc;

		ins[s.top()]=0;

		s.pop();

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

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

		int x,y;scanf("%d%d",&x,&y);

		addl(x*2-1,y*2);addl(y*2-1,x*2);

	}

	cnt=2*n;

	for(int i=1;i<=k;i++){

		int w,x;scanf("%d",&w);

		v[i].push_back(0);

		for(int j=1;j<=w;j++){

			scanf("%d",&x);

			v[i].push_back(x);

		}

		cnt++;addl(cnt,v[i][1]*2-1);

		for(int j=2;j<=w;j++){

			addl(v[i][j]*2,cnt);

			++cnt;addl(cnt,cnt-1);

			addl(cnt,v[i][j]*2-1);

		}

		cnt++;addl(cnt,v[i][w]*2-1);

		for(int j=w-1;j>=1;j--){

			addl(v[i][j]*2,cnt);

			++cnt;addl(cnt,cnt-1);

			addl(cnt,v[i][j]*2-1);

		}

	}

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

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

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

		if(col[2*i]==col[2*i-1])return puts("NIE")&0;

	puts("TAK");return 0;

}

巴特西

P6378-[PA2010]Riddle【2-SAT】

正题

题目大意

解题思路

code

最新文章

热门文章