Steven_MengのBlog

传送门

GDOI

根据$2-SAT$套路,我们要把这个问题转换成依赖性问题,即选择$u$,就必须选$v$。

这个也是非常好转化的,假设$i$,$j$互相憎恶,因为每个党派都必须有一个代表,所以选择了$i$就必须选择$j$所在的党派的另一人,同理,选择了$j$就必须选择$i$所在党派的另一人。

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
#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int dfn[MAXN],low[MAXN],cnt;
stack<int>stk;
int scc,col[MAXN];
void tarjan(int u){
dfn[u]=low[u]=++cnt;
stk.push(u);
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if (!col[v]) low[u]=min(low[u],dfn[v]);
}
if (low[u]==dfn[u]){
++scc;
do{
col[u]=scc;
u=stk.top(),stk.pop();
}while (low[u]!=dfn[u]);
}
}
inline int Other(int x){//返回x的党派的另一人
if (x%2==0) return x-1;
else return x+1;
}
int main(){
int n=read(),m=read();
for (register int i=1;i<=m;++i){
int u=read(),v=read();
AddEdge(u,Other(v));
AddEdge(v,Other(u));
}
for (register int i=1;i<=(n<<1);++i){
if (!dfn[i]) tarjan(i);
}
for (register int i=1;i<=n;++i){
if (col[i*2-1]==col[i*2]){
puts("NIE");
return 0;
}
}
for (register int i=1;i<=n;++i){
int u=i*2-1,v=i*2;
if (col[u]<col[v]) printf("%d\n",u);
else printf("%d\n",v);
}
}

 评论