uva 1391(2-SAT)

题意:有A,B,C三种任务分配给n个宇航员,没个宇航员分配一个任务,只有年龄大于等于平均年龄的宇航员才能分配任务A,年龄小于平均年龄的宇航员才能分配任务B。所有宇航员都能分配任务C。由于有一些宇航员之间存在矛盾所以不能分配同一种任务。现在让你来分配,如果有输出分配情况。

思路:这一看这道题对于没个宇航员有三种状态,但在想一下便可发现对于一个宇航员来说年龄是唯一的,所以A,B中只能选一个。这样一来状态就变成2个了。转化成了2-SAT问题。

代码如下:

uva 1391(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 }
View Code

uva 1391(2-SAT)

上一篇:Unix Shell_Oracle EBS基于主机文件Host开发详解(案例)


下一篇:Titanium开发环境搭建第二个坑