本文共 2777 字，大约阅读时间需要 9 分钟。

为什么我要来学这种鬼畜的东西啊

每个点只有选和不选两种状态,那么拆点

$a_i$表示选第$i$个点作为关键点,$a_i^{\prime }$表示不选

对于边的限制

那么对于一条边$(i,j)$,连边$(a_i^{\prime },a_j)$和$(a_j^{\prime },a_i)$

表示其中一个不选,另一个必选。

对于每个部分的限制

这个暴力一点,对于当前部分的每个点

让这个点选的状态向所有其他点不选的状态连边,表示只能同时选一个

然而这样是$O(n^2)$的连边

考虑优化,其实对于一个部分,设其中的点集是$[1,i]$

那么点$k$如果选,$k$需要向$[1,k-1]$不选的状态连边,向$[k+1,i]$不选的状态连边

我们考虑一下前缀和优化

新建节点$pr{e}_i$表示$[1,i]$中恰好有一个点成为关键点

$pr{e}_i^{\prime }$表示$[1,i]$中没有一个点是关键点

连边$(a_i,pr{e}_i),(pr{e}_i^{\prime },a_i^{\prime })$

显然,自己是关键点,$[1,i]$必须恰有一个点是关键点。

若$[1,i]$没有一个点是关键点,那么自己必定不是关键点$

连边$(pr{e}_{i-1},pr{e}_i),(pr{e}_i^{\prime },pr{e}_{i-1}^{\prime })$

显然,$[1,i-1]$已经满足了,那么$[1,i]$也必须满足恰有一个关键点

$[1,i]$没有一个关键点,那么$[1,i-1]$也必须没有关键点

连边$(a_i,pr{e}_{i-1}^{\prime }),(pr{e}_{i-1},a_i^{\prime })$

显然,自己成为关键点,必须满足$[1,i-1]$没有点是关键点

$[1,i-1]$有点是关键点,那么自己就不能是关键点

经过上面的六条限制,已经满足了所有的要求

非常巧妙。

#include 
   
    using namespace std;const int maxn = 3e7+10;struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt] = ( edge ){
   v,head[u]},head[u] = cnt;}int n,m,k;int dfn[maxn],low[maxn],stac[maxn],vis[maxn],scc[maxn],sc,id,top;void tarjan(int u){
   	vis[u] = 1, stac[++top] = u, low[u] = dfn[u] = ++id;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( !dfn[v] )		{
   			tarjan(v);			low[u] = min( low[u],low[v] );		}		else if( vis[v] )			low[u] = min( low[u],dfn[v] );	}	if( low[u]==dfn[u] )	{
   		sc++; int temp;		while( temp = stac[top--] )		{
   			scc[temp] = sc, vis[temp] = 0;			if( temp == u )	break;		}	}}int T(int x){
    return x; }int F(int x){
    return x+n; }int preT(int x){
    return x+2*n; }int preF(int x){
    return x+3*n; }int a[maxn];int main(){
   	cin >> n >> m >> k;	for(int i=1;i<=m;i++)	{
   		int l,r; scanf("%d%d",&l,&r);		add( F(l),T(r) ); add( F(r),T(l) );	}	for(int i=1;i<=k;i++)	{
   		int lim; scanf("%d",&lim);		for(int j=1;j<=lim;j++)		{
   			scanf("%d",&a[j] );			add( T(a[j]),preT(a[j]) ); add( preF(a[j]),F(a[j]) );		}		for(int j=2;j<=lim;j++)		{
   			add( preT(a[j-1]),preT(a[j]) );add( preF(a[j]),preF(a[j-1]) );			add( T(a[j]),preF(a[j-1]) ); add( preT(a[j-1]),F(a[j]) );		}	}	for(int i=1;i<=4*n;i++)		if( !dfn[i] )	tarjan(i);	for(int i=1;i<=n;i++)	{
   		if( scc[T(i)]==scc[F(i)] ){
    puts("NIE"); return 0; }		if( scc[preT(i)]==scc[preF(i)] ){
    puts("NIE"); return 0; }	}	cout << "TAK";}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115429145 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！