Astronauts（2 - sat）

1391 - Astronauts

Time limit: 3.000 seconds

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 1n100000 <tex2html_verbatim_mark>and 1m100000 <tex2html_verbatim_mark>. The number n <tex2html_verbatim_mark>is the number of astronauts. The next n <tex2html_verbatim_mark>lines specify the age of then <tex2html_verbatim_mark>astronauts; each line contains a single integer number between 0 and 200. The next m <tex2html_verbatim_mark>lines contains two integers each, separated by a space. A line containing i <tex2html_verbatim_mark>and j <tex2html_verbatim_mark>(1i, jn) <tex2html_verbatim_mark>means that the i <tex2html_verbatim_mark>-th astronaut and the j <tex2html_verbatim_mark>-th astronaut hate each other.

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

 

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 <tex2html_verbatim_mark>-th line describes which mission the i <tex2html_verbatim_mark>-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

 

       题意：

       给出 N（1 ~ 100000） 个人，M （1 ~ 100000）条互相讨厌的两个人。后给出这 N 个人的年龄（0 ~ 200），每个人都必须完成 A，B，C 中的其中一个任务，A任务条件为 年龄 大于等于年龄平均值，B任务条件为小于年龄平均值，C任务没有特殊条件。互相讨厌的两个人不能同时做同一个任务。问能否合适安排的任务内容满足所有的条件，能则输出每个人的任务。不能则输出 No solution. 。

 

       思路：

       2 - sat。根据 a 和 b的讨厌关系可以确定一种确定的关系，若 a 和 b 在相同的年龄段（两个时间段），则 a 选 A 或者 B 的话，则 b 必须选 C；b 选 A 或者 B 的话，则 a 必须选 C；a 选 C 的话，b 必须选 A 或者 B；b 选 C 的话，a 必须选 A 或者 B；可以确定四种关系。若 a 和 b 不在同一个年龄段，则 a  选 C 的话，b 必须选 A 或者 B； b 选 C 的话，b 必须选 A 或者 B；可以确定两种关系。根据这个就可以建图了。最后 2 - sat 求出答案即可。

       另外，判断年龄是否大于平均值，必须要用 age [ i ] * N > sum ，直接除以取平均值是不够准确的。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 100005 * 2;
const int EMAX = NMAX * 4;

int n, m, x;
int age[NMAX];
vector<int> v[NMAX];

int scc_cnt, dfs_clock;
int pre[NMAX], low[NMAX], cmp[NMAX];
stack<int> s;

void dfs (int u) {
        pre[u] = low[u] = ++dfs_clock;
        s.push(u);

        for (int i = 0; i < v[u].size(); ++i) {
                if (!pre[ v[u][i] ]) {
                        dfs( v[u][i] );
                        low[u] = min(low[u], low[ v[u][i] ]);
                } else if (!cmp[ v[u][i] ]) {
                        low[u] = min(low[u], pre[ v[u][i] ]);
                }
        }

        if (low[u] == pre[u]) {
                ++scc_cnt;
                for ( ;;) {
                        int x = s.top(); s.pop();
                        cmp[x] = scc_cnt;
                        if (x == u) break;
                }
        }
}

void scc() {
        scc_cnt = dfs_clock = 0;
        memset(pre, 0, sizeof(pre));
        memset(cmp, 0, sizeof(cmp));

        for (int i = 1; i <= 2 * n; ++i) {
                if (!pre[i]) dfs(i);
        }
}

int main() {
        while (~scanf("%d%d", &n, &m) && (n + m)) {
                x = 0;
                for (int i = 1; i <= 2 * n; ++i)
                        v[i].clear();

                for (int i = 1; i <= n; ++i) {
                        scanf("%d", &age[i]);
                        x += age[i];
                }

                while (m--) {
                        int a, b;
                        scanf("%d%d", &a, &b);
                        if ( (age[a] * n >= x && age[b] * n >= x) ||
                             (age[a] * n < x && age[b] * n < x) ) {
                                v[a].push_back(n + b);
                                v[b].push_back(n + a);
                                v[n + a].push_back(b);
                                v[n + b].push_back(a);
                        } else {
                                v[n + a].push_back(b);
                                v[n + b].push_back(a);
                        }
                }

                scc();

                int temp = 0;
                for (int i = 1; i <= n; ++i) {
                        if (cmp[i] == cmp[i + n]) {
                                printf("No solution.\n");
                                temp = 1;
                                break;
                        }
                }

                if (!temp) {
                        for (int i = 1; i <= n; ++i) {
                                if (cmp[i] < cmp[i + n]) {
                                        if (age[i] * n >= x) printf("A\n");
                                        else printf("B\n");
                                } else printf("C\n");
                        }
                }
        }
        return 0;
}