zcmimi's blog

查看原题

点击跳转

首先每条边(x,y)至少有一个端点是关键点

条件 连边
x,y任选一个 \neg x\to y,\neg y\to x

接下来是对每部分进行连边

若将每个点向该部分中出它以外的所有点连边,复杂度为\mathcal O(n^2)

我们可以前缀优化建图

设该部分为a_1,a_2,\dots,a_w

对每个点a_i新增一个状态pre_{a_i}表示a_{1\sim i}中有没有被选为关键点

条件 连边
a_i,pre_{a_i}必须同时选 a_i\to pre_{a_i},\neg pre_{a_i}\to \neg a_i
pre_{a_{i-1}},pre_{a_i}必须同时选 pre_{a_{i-1}}\to pre_{a_i},\neg pre_{a_{i-1}}\to \neg pre_{a_i}
pre_{a_{i-1}},a_i不能同时选 pre_{a_{i-1}}\to \neg a_i,a_i\to \neg pre_{a_{i-1}}

这样就可以\mathcal O(n)连边了

#include<bits/stdc++.h>
const int N=4000011;
int n,m,k,cnt,head[N];
struct edge{int to,nxt;}e[N*2];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int dfn[N],low[N],sz,st[N],tp,bl[N],tt;
bool v[N];
void cmin(int&x,int y){if(y<x)x=y;}
void tarjan(int x){
    dfn[x]=low[x]=++sz;st[++tp]=x;v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(!dfn[to])tarjan(to),cmin(low[x],low[to]);
        else if(v[to])cmin(low[x],dfn[to]);
    if(low[x]==dfn[x]){
        ++tt;
        while(int k=st[tp--]){
            bl[k]=tt;v[k]=0;
            if(k==x)break;
        }
    }
}
#define neg(x) x+n
#define p(x) x+n+n
#define negp(x) x+n+n+n
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int x,y,w,lst;
    for(int i=1;i<=m;++i)
        scanf("%d%d",&x,&y),
        add(neg(x),y),add(neg(y),x);
    while(k--){
        scanf("%d",&w);lst=-1;
        while(w--){
            scanf("%d",&x);
            add(x,p(x)),add(negp(x),neg(x));
            if(~lst){
                add(p(lst),p(x)),add(negp(x),negp(lst)),
                add(p(lst),neg(x)),add(x,negp(lst));
            }
            lst=x;
        }
    }
    for(int i=1;i<=n*4;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i)
        if(bl[i]==bl[neg(i)]||bl[p(i)]==bl[negp(i)])return puts("NIE"),0;
    puts("TAK");
}
LG 6378 [PA2010]Riddle
comment评论
Search
search