LA 3713 宇航员分组

题目链接：http://vjudge.net/contest/142615#problem/B

题意：有A,B,C三个人物要分配个N个宇航员，每个宇航员恰好要分配一个任务，设平均年龄为X，只有年龄大于或等于X的宇航员才能分配任务A。只有年龄严格小于X的宇航员才能分配任务B。而任务C没有限制。有M对宇航员相互讨厌，因此不能分配到同一任务。编程找出一个满足上述所有要求的任务分配方案。

分析：

2-SAT。

建图：

肯定是不能同时去 C 的

同一类的话：

那么就是2a或者2b了，到底是哪个，就得看年龄了。

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn =  + ;

struct TwoSAT

{

    int n;

    vector<int> G[maxn*];

    bool mark[maxn*];

    int S[maxn*], c;

    bool dfs(int x)

    {

        if (mark[x^]) return false;

        if (mark[x]) return true;

        mark[x] = true;

        S[c++] = x;

        for (int i = ; i < G[x].size(); i++)

            if (!dfs(G[x][i])) return false;

        return true;

    }

    void init(int n)

    {

        this->n = n;

        for (int i = ; i < n*; i++) G[i].clear();

        memset(mark, , sizeof(mark));

    }

    // x = xval or y = yval

    void add_clause(int x, int xval, int y, int yval)

    {

        x = x *  + xval;

        y = y *  + yval;

        G[x^].push_back(y);

        G[y^].push_back(x);

    }

    bool solve()

    {

        for(int i = ; i < n*; i += )

            if(!mark[i] && !mark[i+])

            {

                c = ;

                if(!dfs(i))

                {

                    while(c > ) mark[S[--c]] = false;

                    if(!dfs(i+)) return false;

                }

            }

        return true;

    }

};

int n, m, total_age, age[maxn];

int is_young(int x)

{

    return age[x] * n < total_age;

}

TwoSAT solver;

int main()

{

    while(scanf("%d%d", &n, &m) ==  && n && m)

    {

        total_age = ;

        for(int i = ; i < n; i++)

        {

            scanf("%d", &age[i]);

            total_age += age[i];

        }

        solver.init(n);

        for(int i = ; i < m; i++)

        {

            int a, b;

            scanf("%d%d", &a, &b);

            a--;

            b--;

            if(a == b) continue;

            solver.add_clause(a, , b, ); // 不能同去任务C

            if(is_young(a) == is_young(b)) // 同类宇航员

                solver.add_clause(a, , b, ); // 不能同去任务A或者任务B

        }

        if(!solver.solve()) printf("No solution.\n");

        else for(int i = ; i < n; i++)

                if(solver.mark[i*]) printf("C\n"); // x[i]=false，去任务C

                else if(is_young(i)) printf("B\n"); // x[i]=true的年轻宇航员去任务B

                else printf("A\n"); // x[i]=true的年长宇航员去任务A

    }

    return ;

}