题意：有A，B，C三种任务分配给n个宇航员，没个宇航员分配一个任务，只有年龄大于等于平均年龄的宇航员才能分配任务A，年龄小于平均年龄的宇航员才能分配任务B。所有宇航员都能分配任务C。由于有一些宇航员之间存在矛盾所以不能分配同一种任务。现在让你来分配，如果有输出分配情况。
思路：这一看这道题对于没个宇航员有三种状态，但在想一下便可发现对于一个宇航员来说年龄是唯一的，所以A，B中只能选一个。这样一来状态就变成2个了。转化成了2-SAT问题。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-01 14:14 5 * Filename : uva_1391.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 200000+10; 34 vector<int> Map[LEN], rMap[LEN], vs; 35 int n, m, vis[LEN], sccn[LEN], age[LEN]; 36 double avg; 37 38 void dfs(int v){ 39 vis[v] = 1; 40 for(int i=0; i<Map[v].size(); i++) 41 if(!vis[Map[v][i]]) dfs(Map[v][i]); 42 vs.PB(v); 43 } 44 45 void rdfs(int v, int f){ 46 vis[v] = 1; 47 sccn[v] = f; 48 for(int i=0; i<rMap[v].size(); i++) 49 if(!vis[rMap[v][i]]) rdfs(rMap[v][i], f); 50 } 51 52 int scc(){ 53 memset(vis, 0, sizeof vis); 54 vs.clear(); 55 for(int i=0; i<2*n; i++) if(!vis[i]) dfs(i); 56 memset(vis, 0, sizeof vis); 57 int k = 0; 58 for(int i = vs.size()-1; i>=0; i--) if(!vis[vs[i]]) rdfs(vs[i], k++); 59 return k; 60 } 61 62 void solve() 63 { 64 scc(); 65 for(int i=0; i<2*n; i+=2) 66 if(sccn[i] == sccn[i+1]){ 67 printf("No solution.\n"); 68 return ; 69 } 70 for(int i=0; i<n; i++){ 71 if(sccn[i*2] > sccn[i*2+1]) printf("%c\n", age[i]>=avg?‘A‘:‘B‘); 72 else printf("C\n"); 73 } 74 } 75 76 void addedge(int a, int b){ 77 Map[a].PB(b); 78 rMap[b].PB(a); 79 } 80 81 int main() 82 { 83 // freopen("in.txt", "r", stdin); 84 85 int a, b; 86 while(scanf("%d%d", &n, &m)!=EOF){ 87 if(!n && !m) break; 88 for(int i=0; i<LEN; i++) Map[i].clear(); 89 for(int i=0; i<LEN; i++) rMap[i].clear(); 90 avg = 0; 91 for(int i=0; i<n; i++){ 92 scanf("%d", &age[i]); 93 avg += age[i]; 94 } 95 avg /= n; 96 for(int i=0; i<m; i++){ 97 scanf("%d%d", &a, &b);a--;b--; 98 if((age[a] >= avg && age[b] >= avg) || (age[a] < avg && age[b] < avg)){ 99 addedge(a*2, b*2+1); 100 addedge(b*2, a*2+1); 101 } 102 addedge(a*2+1, b*2); 103 addedge(b*2+1, a*2); 104 } 105 solve(); 106 } 107 return 0; 108 }