uva 1391（2-SAT）-白红宇

uva 1391（2-SAT）

阅读量：6687 次

发布时间：2019-06-25

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

题意：有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 
      
        10 #include 
       
         11 #include 
        
          12 #include 
         
           13 #include 
          
            14 #include 
           
             15 #include 
            
              16 #include 
             
               17 #include 
              
                18 #include 
               
                 19 #include 
                 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
                 
                   pii; 26 typedef pair
                  
                    puu; 27 typedef pair
                   
                     pid; 28 typedef pair
                    
                      pli; 29 typedef pair
                     
                       pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 200000+10; 34 vector
                      
                        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
                       
                        =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
                        
                          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
                         
                          = 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

转载于:https://www.cnblogs.com/shu-xiaohao/p/3536997.html

你可能感兴趣的文章