题意
有A,B,C三个任务要分配给n个宇航员，其中每个宇航员恰好要分配一个任务。设所有n个宇航员的平均年龄为x，只有年龄大于或等于x的宇航员才能分配任务A；只有年龄严格小于x的宇航员才能分配任务B，而任务C没有限制。有m对宇航员相互讨厌，因此不能分配到同一任务。编程找出一个满足上述所有要求的任务分配方案。
分析
这个题应该算是比较裸的2-sat了。
对于每个宇航员来说，他的年龄要么大于x要么小于x，所有他只能从A或者B里面选择一个。因此每个宇航员可以选择的任务只有两个A或者B 和C，对应2-sat问题中每个布尔型变量的真和假。有m对宇航员相互讨厌对应2-sat问题中的m条限制。如果两个宇航员年龄都大于x或者都小于x，我们称这两个宇航员为同一种类型。那么xi和xj必须不相同。则用两个条件进行限制。 “xi为真或者xj为真”，“xi为假或者xj为假”。如果两个宇航员为不同类型，那么只需要一个限制“xi为真或者xj为真”。
下面是代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector> using namespace std;
const int maxn=+;
struct TwoSAT{
int n;
vector<int>G[*maxn];
bool mark[maxn*];
int S[maxn*],c;
bool dfs(int x){
if(mark[x^])return false;
if(mark[x])return true;
mark[x]=true;
S[c++]=x;
for(int i=;i<G[x].size();i++){
if(!dfs(G[x][i]))return false;
}
return true;
}
void init(int n){
this->n=n;
for(int i=;i<n*;i++)G[i].clear();
memset(mark,,sizeof(mark));
}
void add_clause(int x,int xval,int y,int yval){
x=x*+xval;
y=y*+yval;
G[x^].push_back(y);
G[y^].push_back(x);
} bool solve(){
for(int i=;i<n*;i+=){
if(!mark[i]&&!mark[i+]){
c=;
if(!dfs(i)){
while(c>)mark[S[--c]]=false;
if(!dfs(i+))return false;
}
}
}
return true;
}
}solver;
int age[maxn],n,m,X;
int kase;
int main(){
kase=;
while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
if(kase)printf("\n");
++kase;
X=;
solver.init(n);
for(int i=;i<n;i++){
scanf("%d",&age[i]);
X+=age[i];
}
int x,y;
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
x--,y--;
if(age[x]*n>=X&&age[y]*n>=X){
solver.add_clause(x,,y,);
solver.add_clause(x,,y,);
}
if(age[x]*n<X&&age[y]*n<X){
solver.add_clause(x,,y,);
solver.add_clause(x,,y,);
}
else{
solver.add_clause(x,,y,);
}
}
if(!solver.solve()){
printf("No solution.");
continue;
}
for(int i=;i<n;i++){
if(solver.mark[*i+]){
if(age[i]*n>=X){
printf("A\n");
}else{
printf("B\n");
}
}else{
printf("C\n");
}
}
}
return ;
}