题意：给出一些宇航员他们的年龄，x是他们的平均年龄，其中A任务只能给年龄大于等于x的人，B任务只能给小于x的人，C任务没有限制。再给出m对人，他们不能同任务。现在要你输出一组符合要求的任务安排。
思路：2SAT。
设Ai表示第i个人的任务，如果i的年龄大于等于x，那么Ai=true表示分到A任务，flase表示分到C任务。如果i年龄小于x则Ai=true表示分到B任务，flase表示分到C任务。
考虑对于这m对里的每对人，如果他们是同组的，那么（Ai并非Aj）或（非Ai并Aj）等价于 （非Ai或非Aj）并（Ai或Aj）
如果他们是不同组的，那么只要他们都不是C任务就行，即非（非Ai并非Aj）等价于（Ai或Aj）
这样就可以用2SAT做了。注意平均年龄x要用浮点数。
我用的是LRJ的模板，2i表示Ai=false，2i+1表示Ai=true
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;
;
struct TwoSAT
{
int n;
vector<];
];
],c;
bool dfs(int x)
{
]) return false;
if(mark[x]) return true;
mark[x]=true;
S[c++]=x;
; i<G[x].size(); ++i)
if(!dfs(G[x][i])) return false;
return true;
}
void init(int n)
{
this->n=n;
; 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()
{
; i<n*; i+=)
{
])
{
c=;
if(!dfs(i))
{
) mark[S[--c]]=false;
)) return false;
}
}
}
return true;
}
};
TwoSAT solver;
];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m) break;
;
; i<n; ++i)
{
scanf("%d",&age[i]);
x+=age[i];
}
x/=n;
solver.init(n);
; i<m; ++i)
{
int a,b;
scanf("%d%d",&a,&b);
a--;
b--;
if((age[a]>=x&&age[b]>=x)||(age[a]<x&&age[b]<x))
{
solver.add_clause(a,,b,);
solver.add_clause(a,,b,);
}
else
solver.add_clause(a,,b,);
}
if(!solver.solve()) puts("No solution.");
else
{
; i<*n; i+=)
if(solver.mark[i])
printf("C\n");
else
printf(]>=x?'A':'B');
}
}
;
}