题目链接
【题意】
有A,B,C3个任务要分给n名宇航员。其中每个宇航员要恰好分配一个任务，所有的n个宇航员平均年龄是x，只有年龄大于等于x的宇航员可以做任务A，年龄小于x的宇航员可以做任务B，任务C没有限制，有m对宇航员相互讨厌，因此不能分配到同一个任务，编程找出一个满足上述所有要求的任务分配方案，无解输出”No solution.”【思路】
对于每个宇航员来讲只有两种选择，要么做任务A/B，要么做任务C，可以用x[i]表示第i个宇航员的分配方案，x[i]=true表示做A/B，x[i]==false表示做C。如果两个宇航员u,v互相讨厌的话，一种情况是它们同属于一种年龄类型，即u,v都是在A,C中选择或B,C中做选择，这时只能让x[u]!=x[v]，等价于x[u]==0或x[v]==0,x[u]==1或x[v]==1；如果他们不是同种类型，那么只要让x[u]==1或x[v]==1即可，这样就建立了一个2-SAT模型。#includeusing namespace std;const int maxn = 100050;int n, m;vector g[maxn * 2];bool mark[maxn * 2];int s[maxn * 2], top;void init() { for (int i = 0; i < n * 2; ++i) g[i].clear(); memset(mark, 0, sizeof(mark));}void add(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 dfs(int x) { if (mark[x ^ 1]) return false; if (mark[x]) return true; mark[x] = true; s[top++] = x; for (int i = 0; i < g[x].size(); ++i) { if (!dfs(g[x][i])) return false; } return true;}bool solve() { for (int i = 0; i < n * 2; i += 2) { if (!mark[i] && !mark[i + 1]) { top = 0; if (!dfs(i)) { while (top > 0) mark[s[--top]] = false; if (!dfs(i + 1)) return false; } } } return true;}int age[maxn], sum;bool issame(int u, int v) { if (n*age[u] < sum && n*age[v] < sum) return true; if (n*age[u] >= sum && n*age[v] >= sum) return true; return false;}int main() { while (scanf("%d%d", &n, &m) == 2) { if (0 == n && 0 == m) break; sum = 0; for (int i = 0; i < n; ++i) { scanf("%d", &age[i]); sum += age[i]; } init(); for (int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); --u, --v; add(u, 1, v, 1); if (issame(u, v)) add(u, 0, v, 0); } if (!solve()) printf("No solution.\n"); else { for (int i = 0; i < n; ++i) { if (mark[2 * i]) puts("C"); else printf("%c\n", n*age[i] >= sum ? 'A' : 'B'); } } } return 0;}