UVA Live 3713 Astronauts （2-SAT）

用布尔变量表示状态，把限制条件转化为XνY的形式以后跑2SAT，根据变量取值输出方案。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

#define PB push_back
bool vis[maxn*2];
vector<int> G[maxn*2];
int N,S[maxn*2],top;
void initGraph(int n)
{
    N = n*2;
    for(int i = 0; i < N; i++) G[i].clear();
    memset(vis,0,sizeof(bool)*(n<<1|1));
}

bool dfs(int x)
{
    if(vis[x^1]) return false;
    if(vis[x]) return true;
    vis[x] = true;
    S[top++] = x;
    for(int i = 0; i < (int)G[x].size(); i++){
        if(!dfs(G[x][i])) return false;
    }
    return true;
}

bool twoSAT()
{
    for(int i = 0; i < N; i+=2){
        if(!vis[i]&&!vis[i^1]){
            top = 0;
            if(!dfs(i)){
                while(top>0) vis[S[--top]] = false;
                if(!dfs(i^1)) return false;
            }
        }
    }
    return true;
}

void add_clause(int x,int xv,int y,int yv)
{
    x = x<<1|xv;
    y = y<<1|yv;
    G[x^1].PB(y);
    G[y^1].PB(x);
}

int tp[maxn];
int age[maxn];
char bin[2][2] = {{'C','B'},{'C','A'}};

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m;
    while(scanf("%d%d",&n,&m),n){
        int sum = 0;
        for(int i = 0; i < n; i++){
            scanf("%d",age+i);
            sum += age[i];
        }
        for(int i = 0; i < n; i++){
            if(age[i]*n >= sum) tp[i] = 1;
            else tp[i] = 0;
        }
        initGraph(n);
        for(int i = 0; i < m; i++){
            int u,v; scanf("%d%d",&u,&v);
            if(tp[--u]^tp[--v]){
                add_clause(u,1,v,1);
            }else {
                add_clause(u,0,v,0);
                add_clause(u,1,v,1);
            }
        }
        if(twoSAT()){
            for(int i = 0; i < N; i+=2){
                putchar(bin[tp[i>>1]][vis[i^1]]);
                putchar('
');
            }
        }else {
            puts("No solution.");
        }
    }
    return 0;
}