BZOJ-2199: [Usaco2011 Jan]奶牛议会

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注