算法：UVA 1391 Astronauts（2-SAT + 输出方案）

算法：UVA 1391 Astronauts（2-SAT + 输出方案）2014-01-10 csdn shuangde800【题目大意】

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

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

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

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

【思路】

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

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

【代码】

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#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<n; ++i）if（belong[i] == belong[i+n]）return false;return true;}void toposort（）{g1.init（）;memset（indeg, 0, sizeof（indeg））;for（int i=0; i<n; ++i）{opp[belong[i]] = belong[i+n];opp[belong[i+n]] = belong[i];}for（int e=0; e<g.size; ++e）{int u = belong[g.E[e].u];int v = belong[g.E[e].v];if（u==v） continue;++indeg[u];g1.addEdge（v, u）;}queue<int>que;memset（color, WHITE, sizeof（color））;for（int i=1; i<=bcnt; ++i）if（！indeg[i]）que.push（i）;while（！que.empty（））{int u = que.front（）;que.pop（）;if（color[u] ！= WHITE） continue;color[u] = RED;color[opp[u]] = BLUE;for（int e=g1.head[u]; e！=-1; e=g1.E[e].next）{int v=g1.E[e].v;if（--indeg[v] == 0）que.push（v）;}}// outputfor（int i=0; i<n; ++i）{if（color[belong[i]] == RED）{if（age[i]*n < sum） puts（"B"）;else puts（"A"）;}else{puts（"C"）;}}}private:void tarjan（const int u）{int v;dfn[u] = low[u] = ++idx;instack[u] = true;sta[top++] = u;for（int e=g.head[u]; e！=-1; e=g.E[e].next）{v = g.E[e].v;if（dfn[v] == -1） tarjan（v）, low[u]=min（low[u], low[v]）;else if（instack[v]） low[u]=min（low[u], dfn[v]）;}if（low[u] == dfn[u]）{++bcnt;do{v=sta[--top];instack[v] = false;belong[v] = bcnt;}while（u ！= v）;}}void scc（）{idx = bcnt = top = 0;memset（instack, 0, sizeof（instack））;memset（dfn, -1, sizeof（dfn））;for（int i=0; i<2*n; ++i）if（dfn[i] == -1）tarjan（i）;}private:int idx, top, bcnt;int low[VN],dfn[VN],belong[VN],sta[VN];bool instack[VN];int color[VN], indeg[VN], opp[VN];}sat;int main（）{while（~scanf（"%d%d", &n, &m） && n+m）{sum = 0;for（int i=0; i<n; ++i）{scanf（"%d", &age[i]）;sum += age[i];}g.init（）;int a, b;for（int i=0; i<m; ++i）{scanf（"%d%d", &a, &b）;--a; --b;if（age[a]*n < sum && age[b]*n < sum）{ //小，小g.addEdge（a, b+n）;g.addEdge（a+n, b）;g.addEdge（b, a+n）;g.addEdge（b+n, a）;}else if（age[a]*n < sum && age[b]*n >= sum）{//小，大g.addEdge（a+n, b）;g.addEdge（b+n, a）;}else if（age[a]*n >= sum && age[b]*n < sum）{//大，小g.addEdge（a+n, b）;g.addEdge（b+n, a）;}else{ // 大，大g.addEdge（a, b+n）;g.addEdge（a+n, b）;g.addEdge（b, a+n）;g.addEdge（b+n, a）;}}if（！sat.check（）） puts（"No solution."）;else sat.toposort（）;}return 0;}