LA 3713 宇航员分组

题意：

有A、B、C 3个任务要分配给n个宇航员，其中每个宇航员恰好要分配一个任务。设所有n个宇航员的平均年龄为x，只有年龄大于或等于x的宇航员才能分配任务A；只有年龄严格小于x的宇航员才能分配任务B，而任务C没有限制。有m对宇航员相互讨厌，因此不能分配到同一任务。编程找出一个满足上述所有要求的任务分配方案。

思路：

每个宇航员要么选C，要么选A和B当中的一个（看年龄大小）。

对m对相互厌恶的宇航员拆点连边。

如果他们属于同一个类型，那么Xi,Xj必须不同，Xi为真或Xj为真，Xi为假或Xj为假。前者表示至少一个为true，后者表示至少一个为false。这样只可能是两者一个为true,一个为false了。如果是不同的类型，那么唯一的冲突就是Xi，Xj均为false（即都去做任务C）。那么只需要“Xi为真或Xj为真”即可排除这种冲突。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 using namespace std;
 11 
 12 const int maxn=100000+5;
 13 
 14 int n,m;
 15 int age[maxn];
 16 
 17 struct TwoSAT
 18 {
 19     int n;
 20     vector<int> G[2*maxn];
 21     bool mark[2*maxn];
 22     int S[2*maxn],c;
 23 
 24     bool dfs(int x)
 25     {
 26         if(mark[x^1])  return false;
 27         if(mark[x])  return true;
 28         mark[x]=true;
 29         S[c++]=x;
 30         for(int i=0;i<G[x].size();i++)
 31             if(!dfs(G[x][i]))   return false;
 32         return true;
 33     }
 34 
 35     void init(int n)
 36     {
 37         this->n=n;
 38         for(int i=0;i<2*n;i++)   G[i].clear();
 39         memset(mark,0,sizeof(mark));
 40     }
 41 
 42     void add_clause(int x,int xval,int y,int yval)
 43     {
 44         x = x*2 + xval;
 45         y = y*2 + yval;
 46         G[x^1].push_back(y);
 47         G[y^1].push_back(x);
 48     }
 49 
 50     bool solve()
 51     {
 52         for(int i=0;i<2*n;i+=2)
 53             if(!mark[i] && !mark[i+1])
 54         {
 55             c=0;
 56             if(!dfs(i))
 57             {
 58                 while(c>0)  mark[S[--c]]=false;
 59                 if(!dfs(i+1))   return false;
 60             }
 61         }
 62         return true;
 63     }
 64 }solver;
 65 
 66 bool age_judge(int a,int x)
 67 {
 68     if(a*n>=x)  return true;
 69     else return false;
 70 }
 71 
 72 int main()
 73 {
 74     //freopen("D:\input.txt","r",stdin);
 75     while(~scanf("%d%d",&n,&m)&&n)
 76     {
 77         solver.init(n);
 78         int sum=0;
 79         for(int i=0;i<n;i++)
 80         {
 81             scanf("%d",&age[i]);
 82             sum+=age[i];
 83         }
 84         while(m--)
 85         {
 86             int u,v;
 87             scanf("%d%d",&u,&v);
 88             u--; v--;
 89             solver.add_clause(u,1,v,1);
 90             if(age_judge(age[u],sum)==age_judge(age[v],sum))  solver.add_clause(u,0,v,0);
 91         }
 92         if(!solver.solve())   puts("No solution.");
 93         else for(int i=0;i<n;i++)
 94         {
 95             if(solver.mark[2*i])  puts("C");
 96             else if(age_judge(age[i],sum))  puts("A");
 97             else puts("B");
 98         }
 99     }
100     return 0;
101 }