uva1391 - Astronauts 2-SAT

The Bandulu Space Agency (BSA) has plans for the following three space missions:

• Mission A: Landing on Ganymede, the largest moon of Jupiter.
• Mission B: Landing on Callisto, the second largest moon of Jupiter.
• Mission C: Landing on Titan, the largest moon of Saturn.

Your task is to assign a crew for each mission. BSA has trained a number of excellent astronauts; everyone of them can be assigned to any mission. However, if two astronauts hate each other, then it is not wise to put them on the same mission. Furthermore, Mission A is clearly more prestigious than Mission B; who would like to go to the second largest moon if there is also a mission to the largest one? Therefore, the assignments have to be done in such a way that only young, inexperienced astronauts go to Mission B, and only senior astronauts are assigned to Mission A. An astronaut is considered young if their age is less than the average age of the astronauts and an astronaut is senior if their age is at least the averageage. Every astronaut can be assigned to Mission C, regardless of their age (but you must not assign two astronauts to the same mission if they hate each other).

Input 

The input contains several blocks of test cases. Each case begins with a line containing two integers 1

n

100000 and 1

m

100000. The number n is the number of astronauts. The next n lines specify the age of the n astronauts; each line contains a single integer number between 0 and 200. The next m lines contains two integers each, separated by a space. A line containing i and j (1

i, j

n) means that the i-th astronaut and the j-th astronaut hate each other.

The input is terminated by a block with n = m = 0.

Output 

For each test case, you have to output n lines, each containing a single letter. This letter is either `A', `B', or `C'. The i-th line describes which mission the i-th astronaut is assigned to. Astronauts that hate each other should not be assigned to the same mission, only young astronauts should be assigned to Mission B and only senior astronauts should be assigned to Mission A. If there is no such assignment, then output the single line `No solution.' (without quotes).

Sample Input 

16 20
21
22
23
24
25
26
27
28
101
102
103
104
105
106
107
108
1 2
3 4
5 6 
7 8
9 10
11 12
13 14
15 16
1 10
2 9
3 12
4 11
5 14
6 13 
7 16
8 15
1 12
1 13
3 16
6 15
0 0
      

Sample Output 

B
C
C
B
C
B
C
B
A
C
C
A
C
A
C
A
      

  有A,B,C 3個任務配置設定給N個人，每個人配置設定一個，年齡大于等于平均年齡的隻能配置設定A或C，否則隻能配置設定B或C。有M對人互相讨厭，互相讨厭的人不能配置設定到一樣的任務。

  每個人隻有2種選擇，這就變成了一個2-SAT問題。把年齡大于等于平均年齡的人設為第1類，年齡小于平均年齡的設為第2類。第1類設配置設定A為真，配置設定C為假，第2類人配置設定B為真，C為假。互相讨厭的兩個人u,v如果屬于同一類，那麼就要增加兩次邊，u真或v真，u假或v假，如果兩個人不是同一類，就隻需要增加一次邊，u真或v真。

  2-SAT在搜尋過程中記錄選擇情況，最後再根據每個人的類型輸出對應的答案。

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<algorithm>
#define INF 0x3f3f3f3f
#define eps 1e-9
#define MAXN 100010
#define MAXM 2000010
#define MAXNODE 105
#define MOD 100000
#define SIGMA_SIZE 4
typedef long long LL;
using namespace std;
int T,N,M,sum,age[MAXN],ans[MAXN],type[MAXN];
struct TwoSAT{
    int n,c,S[MAXN*2];
    bool mark[MAXN*2];
    vector<int> 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]=true;
        S[c++]=x;
        int L=G[x].size();
        for(int i=0;i<L;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].push_back(y);
        G[y^1].push_back(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;
            }
            while(c>0) ans[S[--c]>>1]=S[c]%2;
        }
        return true;
    }
}solver;

int main(){
    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)!=EOF&&(N||M)){
        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) type[i]=1;
            else type[i]=2;
        }
        solver.init(N);
        int u,v;
        while(M--){
            scanf("%d%d",&u,&v);
            u--;
            v--;
            if(type[u]==type[v]){
                solver.add_clause(u,1,v,1);
                solver.add_clause(u,0,v,0);
            }
            else solver.add_clause(u,1,v,1);
        }
        if(!solver.solve()) printf("No solution.\n");
        else for(int i=0;i<N;i++){
            if(!ans[i]) printf("C\n");
            else if(type[i]==1) printf("A\n");
            else printf("B\n");
        }
    }
    return 0;
}