[文章目录]
Description
由于对Farmer John的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛 都可以获得自己想要的”为原则，建立了下面的投票系统： M只到场的奶牛 (1<=M<=4000)会给N个议案投票(1<=N<=1,000)。每只 奶牛会对恰好两个议案 B_i and C_i (1 <= B_i <= N;1 <= C_i <= N)投出“是”或“否”（输入文件中的'Y'和'N'）。他们的投票结果分别为VB_i (VB_i in {'Y', 'N'}) and VC_i (VC_i in {'Y', 'N'})。 最后，议案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。例如Bessie给议案1投了赞成'Y'，给议案2投了反对'N'，那么在任何合法的议案通过 方案中，必须满足议案1必须是'Y'或者议案2必须是'N'（或者同时满足）。给出每只奶牛的投票，你的工作是确定哪些议案可以通过，哪些不能。如果不存在这样一个方案， 输出"IMPOSSIBLE"。如果至少有一个解，输出：
Y:如果在每个解中，这个议案都必须通过。
N:如果在每个解中，这个议案都必须驳回。
?:如果有的解这个议案可以通过，有的解中这个议案会被驳回 。
2-sat
建模，对于每对点，我们都进行搜索，记录是否合法。如果有一对点都不合法输出无解，反之，输出所有对点的合法情况。时间复杂度O(nm)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,v[2100],tim;
char ans[1100];
int head[2100],to[10000],nxt[10000],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x)
{
v[x]=tim;
for(int i=head[x];i;i=nxt[i]) if(v[to[i]]!=tim) dfs(to[i]);
}
int main()
{
scanf("%d%d",&n,&m);
char sw1[4],sw2[4]; int a,b;
while(m--)
{
scanf("%d%s%d%s",&a,sw1,&b,sw2);
a=(a<<1)|(sw1[0]=='Y'); b=(b<<1)|(sw2[0]=='Y');
add(a^1,b); add(b^1,a);
}
/*for(int i=1;i<=n;++i)
{
printf("\n%d:",i<<1);
for(int j=head[i<<1];j;j=nxt[j]) printf(" %d",to[j]);
printf("\n%d:",i<<1|1);
for(int j=head[i<<1|1];j;j=nxt[j]) printf(" %d",to[j]);
}*/
for(int i=1;i<=n;++i)
{
tim++; dfs(i<<1); a=1;
for(int j=1;j<=n;++j) if(v[j<<1]==tim&&v[j<<1|1]==tim) {a=0; break;}
tim++; dfs(i<<1|1); b=1;
for(int j=1;j<=n;++j) if(v[j<<1]==tim&&v[j<<1|1]==tim) {b=0; break;}
if(!a&&!b)
{
puts("IMPOSSIBLE");
return 0;
}
if(a&&b) ans[i]='?';
else if(a) ans[i]='N';
else if(b) ans[i]='Y';
}
printf("%s",ans+1);
return 0;
}