训练指南 UVALive - 3713 （2-SAT）

---

layout: post

title: 训练指南 UVALive - 3713 （2-SAT）

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 2-SAT

- 图论

- 训练指南

---

Astronauts

UVALive - 3713

题意

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

题解

如果憎恶就代表不能一起去C，如果年龄相同就代表不能一起去A/B；

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e6+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

struct TwoSAT{

    int n;

    vector<int> G[maxn*2];

    bool mark[maxn*2];

    int S[maxn*2],c;

    bool dfs(int x){

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

        if(mark[x])return true;

        mark[x]=true;

        S[c++]=x;

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

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

        return true;

    }

    void init(int n){

        this->n=n;

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

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

    }

    /// x=xval or y= yval;

    void add_caluse(int x,int xval,int y,int yval){

        x=x*2+xval;

        y=y*2+yval;

        G[x^1].push_back(y);///如果x为真 那么y必须为假;

        G[y^1].push_back(x);///如果y为真 那么x必须为假;

    }

    bool solve(){

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

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

            c=0;

            if(!dfs(i)){

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

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

            }

        }

        return true;

    }

};

int n,a[maxn],m;

TwoSAT solver;

int tol;

int is_young(int x){

    return a[x]*n<tol;

}

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    while(cin>>n>>m&&n&&m){

        tol=0;

        solver.init(n);

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

            cin>>a[i];

            tol+=a[i];

        }

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

            int a,b;

            cin>>a>>b;a--;b--;

            solver.add_caluse(a,1,b,1);

            if(is_young(a)==is_young(b))

                solver.add_caluse(a,0,b,0);

        }

        if(!solver.solve())cout<<"No solution."<<endl;

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

            if(solver.mark[i*2])cout<<"C"<<endl;

        else if(is_young(i))cout<<"B"<<endl;

        else cout<<"A"<<endl;

    }

    return 0;

}