题意
有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为真”。
下面是代码
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <vector> 6 7 using namespace std; 8 const int maxn=100000+10; 9 struct TwoSAT{ 10 int n; 11 vector<int>G[2*maxn]; 12 bool mark[maxn*2]; 13 int S[maxn*2],c; 14 bool dfs(int x){ 15 if(mark[x^1])return false; 16 if(mark[x])return true; 17 mark[x]=true; 18 S[c++]=x; 19 for(int i=0;i<G[x].size();i++){ 20 if(!dfs(G[x][i]))return false; 21 } 22 return true; 23 } 24 void init(int n){ 25 this->n=n; 26 for(int i=0;i<n*2;i++)G[i].clear(); 27 memset(mark,0,sizeof(mark)); 28 } 29 void add_clause(int x,int xval,int y,int yval){ 30 x=x*2+xval; 31 y=y*2+yval; 32 G[x^1].push_back(y); 33 G[y^1].push_back(x); 34 } 35 36 bool solve(){ 37 for(int i=0;i<n*2;i+=2){ 38 if(!mark[i]&&!mark[i+1]){ 39 c=0; 40 if(!dfs(i)){ 41 while(c>0)mark[S[--c]]=false; 42 if(!dfs(i+1))return false; 43 } 44 } 45 } 46 return true; 47 } 48 }solver; 49 int age[maxn],n,m,X; 50 int kase; 51 int main(){ 52 kase=0; 53 while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){ 54 if(kase)printf(" "); 55 ++kase; 56 X=0; 57 solver.init(n); 58 for(int i=0;i<n;i++){ 59 scanf("%d",&age[i]); 60 X+=age[i]; 61 } 62 int x,y; 63 for(int i=1;i<=m;i++){ 64 scanf("%d%d",&x,&y); 65 x--,y--; 66 if(age[x]*n>=X&&age[y]*n>=X){ 67 solver.add_clause(x,0,y,0); 68 solver.add_clause(x,1,y,1); 69 } 70 if(age[x]*n<X&&age[y]*n<X){ 71 solver.add_clause(x,0,y,0); 72 solver.add_clause(x,1,y,1); 73 } 74 else{ 75 solver.add_clause(x,1,y,1); 76 } 77 } 78 if(!solver.solve()){ 79 printf("No solution."); 80 continue; 81 } 82 for(int i=0;i<n;i++){ 83 if(solver.mark[2*i+1]){ 84 if(age[i]*n>=X){ 85 printf("A "); 86 }else{ 87 printf("B "); 88 } 89 }else{ 90 printf("C "); 91 } 92 } 93 } 94 return 0; 95 }