Steven_MengのBlog

洛谷

GDOI

首先,按照$2-SAT$问题的套路,我们要把这个转化成依赖性问题

又发现一只奶牛刚好投两次票,所以只要不满足奶牛的其中一次投票,就要满足另一次,这样就转化成了依赖性问题。

但是,这道题还要输出$”?”$,怎么搞

再看一眼数据范围$1 \le N \le 1000$,这样小的数据范围,暴力都能过。

于是不妨从两个相对的节点$bfs$一遍,如果他们两个都没有矛盾,那么输出$?$,如果一个有矛盾,那么输出$Y/N$,如果都有矛盾,那么输出$IMPOSSIBLE$。

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
72
73
#include <bits/stdc++.h>
#define MAXN 4005
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 vis[MAXN],n,m;
inline int Other(int u){
if (u<=n) return u+n;
else return u-n;
}
inline bool bfs(int s){
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(s);
while (Q.size()){
int u=Q.front();Q.pop();
vis[u]=true;
if (vis[Other(u)]) return false;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (!vis[v]) Q.push(v);
}
}
return true;
}
inline char gc(){
char ch=getchar();
while (ch!='Y'&&ch!='N') ch=getchar();
return ch=='Y';
}
int main(){
n=read(),m=read();
//1 ... n赞成票
//n+1 ... 2*n反对票
for (register int i=1;i<=m;++i){
int u=read(),f1=gc(),v=read(),f2=gc();
AddEdge(u+(!f1)*n,v+f2*n);
AddEdge(v+(!f2)*n,u+f1*n);
}
string Ans="";
for (register int i=1;i<=n;++i){
bool True=bfs(i),False=bfs(Other(i));
if (!True&&!False){
puts("IMPOSSIBLE");
return 0;
}
else if (True&&!False){
Ans+='N';
}
else if (False&&!True){
Ans+='Y';
}
else {
Ans+='?';
}
}
cout<<Ans<<endl;
}

 评论