「BZOJ 3495」PA2010 Riddle

发表于

有 nn 个城镇被分成了 kk 个郡，有 mm 条连接城镇的无向边。要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。

Constraints

1≤n≤1061\leq n \leq 10 ^6 ，0≤m≤1060\leq m \leq 10 ^6 ，1≤k≤n1\leq k \leq n

Solution

每个点 xx 拆成两对点，xx 代表选择 xx 为首都，x+nx+n 表示不选择 xx 为首都，x+2nx+2n 表示 xx 的前缀已包含首都，x+3nx+3n 表示 xx 的前缀不包含首都。

对于每一条原图中无向边 (x,y)(x,y) ，因为至少有一个端点为首都，连边 (x+n,y)(x+n,y) ，(y+n,x)(y+n,x)。

对于每一个点 xx ，连边 (x,x+2n)(x,x+2n) ，(x+3n,x+n)(x+3n,x+n)。

对于每一个点 xx 与它的上一个点 lastlast ，连边方式如下：(last+2n,x+2n)(last+2n,x+2n)，(x+3n,last+3n)(x+3n,last+3n)，(last+2n,x+n)(last+2n,x+n)，(x,last+3n)(x,last+3n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int N=4e6+5;
int n,m,k,cnt,x,y,last,tim,top,color;
int first[N],dfn[N],low[N],sta[N],c[N];
bool vis[N];
struct edge{int to,next;}e[N*3];
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++tim;
    sta[++top]=x;vis[x]=true;
    for(int i=first[x];i;i=e[i].next)
    {
        int to=e[i].to;
        if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]=min(low[x],low[to]));
        else if(vis[to])low[x]=min(low[x],dfn[to]);
    }
    if(low[x]==dfn[x])
    {
        color++;
        while(sta[top]!=x)vis[sta[top]]=false,c[sta[top--]]=color;
        vis[x]=false;c[x]=color;top--;
    }
}
bool check()
{
    for(int i=1;i<=n;i++)
        if(c[i]==c[i+n]||c[i+2*n]==c[i+3*n])return false;
    return true;
}
int main()
{
    n=read();m=read();k=read();
    for(int i=1;i<=m;i++)
    {
        x=read();y=read();
        ins(x+n,y);ins(y+n,x);
    }
    for(int i=1;i<=k;i++)
    {
        x=read();last=0;
        for(int j=1;j<=x;j++)
        {
            y=read();
            ins(y,y+2*n);ins(y+3*n,y+n);
            if(last)
            {
                ins(last+2*n,y+2*n);
                ins(y+3*n,last+3*n);
                ins(last+2*n,y+n);
                ins(y,last+3*n);
            }
            last=y;
        }
    }
    for(int i=1;i<=4*n;i++)if(!dfn[i])tarjan(i);
    if(check())printf("TAK");
    else printf("NIE");
    return 0;
}