本文共 1764 字，大约阅读时间需要 5 分钟。

【】

【题目大意】

有n个宇航员，按照年龄划分，年龄低于平均年龄的是年轻宇航员，而年龄大于等于平均年龄的是老练的宇航员。

现在要分配他们去A，B，C三个空间站，其中A站只有老练的宇航员才能去，而B站是只有年轻的才能去，C站都可以去。

有m对宇航员相互讨厌，不能让他们在同一个空间站工作。

输出每个宇航员应分配到哪个空间站，如果没有则输出No solution.

【思路】

对于每一个宇航员，他都只有两个地方能去：C或者非C（如果是年轻的是B，老练的是A）， 所以是二选一的，可以想到是2-SAT判定问题。

建边时，分好情况加边即可。然后就是套模板了。

【代码】

#include
   
    #include
    
     #include
     
      #include
      
       #define WHITE -1#define RED 1#define BLUE 0using namespace std;const int INF  = 0x3f3f3f3f;const int MAXN = 100010;const int VN = MAXN*2;const int EN = VN*5;int n, m;int age[MAXN];int sum;struct Graph{    int size, head[VN];    struct{int u, v, next; }E[EN];    void init(){size=0; memset(head, -1, sizeof(head)); }    void addEdge(int u, int v){        E[size].u = u;        E[size].v = v;        E[size].next = head[u];        head[u] = size++;    }}g, g1;class Tow_Sat{public:    bool check(){        scc();        for(int i=0; i