UVALive - 3713 Astronauts

给定n个宇航员的年龄，平均年龄为 ave，根据下列要求分配任务：

B任务只能分配给年龄<ave的宇航员；

A任务只能分配给年龄>=ave的宇航员；

C任务可以任意分配。

给定m组互相憎恨的宇航员，要求他们不能分配到同一个任务。能否存在这样的一组任务分配。

每个宇航员都只能分配两种任务中的一种：A或C（年龄大于等于ave），B或C（年龄小于ave)，那么为每个宇航员设立一个变量xi，xi为0表示分配C任务，为1则分配A或B（根据年龄）。

对于互相仇恨的宇航员，如果属于同一类型，那么应满足xi∨xj，非xi∨非xj，表示xi和xj一真一假；如果类型不同只需要满足不同时分配C任务就可：xi∨xj。

直接贴代码好了：

#include <iostream>

#include <sstream>

#include <cstdio>

#include <climits>

#include <cstring>

#include <cstdlib>

#include <string>

#include <stack>

#include <map>

#include <cmath>

#include <vector>

#include <queue>

#include <algorithm>

#define esp 1e-6

#define pi acos(-1.0)

#define pb push_back

#define mp(a, b) make_pair((a), (b))

#define in  freopen("in.txt", "r", stdin);

#define out freopen("out.txt", "w", stdout);

#define print(a) printf("%d\n",(a));

#define bug puts("********))))))");

#define stop  system("pause");

#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)

#define pragma comment(linker, "/STACK:102400000, 102400000")

#define inf 0x0f0f0f0f

using namespace std;

typedef long long  LL;

typedef vector<int> VI;

typedef pair<int, int> pii;

typedef vector<pii,int> VII;

typedef vector<int>:: iterator IT;

const int maxn = 111111;

int A[maxn], tag[maxn];

double sum;

int dblcmp(int x)

{

    if(fabs(x) < esp)

        return 1;

    return x > 0 ? 1 : 0;

}

struct TwoSAT

{

    int mark[maxn*2], S[maxn*2], c, n;

    VI g[maxn*2];

    void init(int n)

    {

        this->n = n;

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

            g[i].clear();

        memset(mark, 0, sizeof(mark));

    }

    bool dfs(int x)

    {

        if(mark[x^1]) return false;

        if(mark[x])    return true;

        mark[x] = 1;

        S[c++] = x;

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

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

        return true;

    }

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

    {

        x = x*2+xval;

        y = y*2+yval;

        g[x^1].pb(y);

        g[y^1].pb(x);

    }

    bool solve()

    {

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

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

            {

                c = 0;

                if(!dfs(i))

                {

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

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

                }

            }

        return true;

    }

    void print_ans(void)

    {

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

        {

            puts(mark[2*i] ? "C" : (tag[i] == 1 ? "A" : "B"));

        }

    }

} sat;

bool check(int x)

{

    return dblcmp(A[x]-sum);

}

int main(void)

{

    int n, m;

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

    {

        sum = 0;

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

            scanf("%d", A+i), sum += A[i];

        sum /= n;

        sat.init(n);

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

            tag[i] = check(i);

        while(m--)

        {

            int u, v;

            scanf("%d%d", &u, &v);

            u--, v--;

            if(tag[u] != tag[v])

            {

                sat.add_clause(u, 1, v, 1);

            }

            else

            {

                sat.add_clause(u, 1, v, 1);

                sat.add_clause(u, 0, v, 0);

            }

        }

        if(sat.solve())

            sat.print_ans();

        else puts("No solution.");

    }

    return 0;

}

巴特西

UVALive - 3713 Astronauts

最新文章

热门文章