UVALive-4452 The Ministers' Major Mess （2-SAT）

题目大意：有n个问题，m个人来投票，没人最多投4票，问该怎样决定才能使每个人都有超过一半的票数被认可？

题目分析：2-SAT问题。如果某个人投的票数少于2，则这两票军被采纳，如果票数至少三票，则最多有一票可以不被采纳，这意味着这个人的投的任意两票之间有矛盾，是“二者取一”的关系。

代码如下：

# include<iostream>
# include<cstdio>
# include<vector>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std;
# define LL long long
# define REP(i,s,n) for(int i=s;i<n;++i)
# define CLS(a,b) memset(a,b,sizeof(a))
# define CLL(a,b,n) fill(a,a+n,b)

const int N=105;
vector<int>G[N<<1];
int n,m,a[5],b[5],must[N+N],mark[N+N],flag[N],s[N+N],cnt;

void add(int x,int u,int y,int v)
{
    x=x*2+u;
    y=y*2+v;
    G[x^1].push_back(y);
    G[y^1].push_back(x);
}

void dfs1(int u)
{
    must[u]=1;
    REP(i,0,G[u].size()) if(!must[G[u][i]]) dfs1(G[u][i]);
}

void clear()
{
    CLS(mark,0);
    REP(i,0,n+n) mark[i]=must[i];
}

bool dfs(int x)
{
    if(mark[x^1]) return false;
    if(mark[x]) return true;
    mark[x]=1;
    s[cnt++]=x;
    REP(i,0,G[x].size()) if(!dfs(G[x][i])) return false;
    return true;
}

bool solve()
{
    for(int i=0;i<n+n;i+=2){
        if(mark[i]&&mark[i+1]) return false;
        if(!mark[i]&&!mark[i+1]){
            cnt=0;
            if(!dfs(i)){
                while(cnt>0) mark[s[--cnt]]=0;
                if(!dfs(i+1)) return false;
            }
        }
    }
    return true;
}

void init()
{
    REP(i,0,n*2) G[i].clear();
    CLS(must,0);
    CLS(mark,0);
}

int main()
{
    int k,cas=0;
    char c;
    while(scanf("%d%d",&n,&m)&&(n+m))
    {
        init();
        CLS(flag,0);
        while(m--)
        {
            scanf("%d",&k);
            REP(i,0,k){
                scanf("%d %c",&a[i],&c);
                --a[i];
                if(c=='y') b[i]=1;
                else b[i]=0;
            }
            if(k<=2){
                REP(i,0,k) must[a[i]*2+b[i]]=1;
            }else
                REP(i,0,k) REP(j,i+1,k) add(a[i],b[i],a[j],b[j]);
        }

        REP(i,0,n+n) if(must[i]) dfs1(i);

        printf("Case %d: ",++cas);
        REP(i,0,n){
            if(must[i*2]||must[i*2+1]) continue;
            clear();
            mark[i*2]=1;
            bool yy1=solve();
            clear();
            mark[i*2+1]=1;
            bool yy2=solve();
            if(yy1&&yy2) flag[i]=1;
        }
        clear();
        if(!solve()){
            printf("impossible
");
            continue;
        }
        REP(i,0,n){
            if(flag[i]) printf("?");
            else if(mark[i*2]) printf("n");
            else printf("y");
        }
        printf("
");
    }
    return 0;
}

UVALive-4452 The Ministers' Major Mess （2-SAT）

相关推荐