转载

UVAlive3713 Astronauts（2-SAT）

题目链接： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18511

【思路】

2-SAT。

设分得A或B类任务为1 C类任务为0，考虑互相讨厌的两人：如果年龄阶段相同，则需要满足a!=b，即(a==1 or b==1)=1 && (a==0 or b==0)=1，如果年龄阶段不同，则需要满足ab不同时为C，即(a==1 or b==1)=1。

【代码】

  1 #include<cstdio>  2 #include<vector>  3 #include<cstring>  4 #include<iostream>  5 #include<algorithm>  6 using namespace std;  7   8   9 const int maxn = 100000+10; 10  11 struct TwoSAT { 12     int n; 13     vector<int> G[maxn*2]; 14     bool mark[maxn*2]; 15     int S[maxn*2],c; 16      17     void init(int n) { 18         this->n=n; 19         for(int i=0;i<n*2;i++) G[i].clear(); 20         memset(mark,0,sizeof(mark)); 21     } 22     void addc(int x,int xval,int y,int yval) { 23         x=x*2+xval; 24         y=y*2+yval; 25         G[x^1].push_back(y); 26         G[y^1].push_back(x); 27     } 28     bool dfs(int x) { 29         if(mark[x^1]) return false; 30         if(mark[x]) return true; 31         mark[x]=true; 32         S[c++]=x; 33         for(int i=0;i<G[x].size();i++) 34             if(!dfs(G[x][i])) return false; 35         return true; 36     } 37     bool solve() { 38         for(int i=0;i<n*2;i+=2) 39             if(!mark[i] && !mark[i+1]) { 40                 c=0; 41                 if(!dfs(i)) { 42                     while(c>0) mark[S[--c]]=false; 43                     if(!dfs(i+1)) return false; 44                 } 45             } 46         return true; 47     } 48 }ts; 49  50 int n,m; 51 int a[maxn]; 52  53 int main() { 54     while(scanf("%d%d",&n,&m)==2 && n) { 55         int u,v,x=0; 56         for(int i=0;i<n;i++) scanf("%d",&a[i]),x+=a[i]; 57         ts.init(n); 58         for(int i=0;i<m;i++) { 59             scanf("%d%d",&u,&v); 60             u--,v--; 61             int k1=a[u]*n<x? 0:1; 62             int k2=a[v]*n<x? 0:1; 63             if(k1==k2) { 64                 ts.addc(u,1,v,1); 65                 ts.addc(u,0,v,0); 66             } 67             else  ts.addc(u,1,v,1); 68         } 69         if(!ts.solve()) printf("No solution./n"); 70         else 71             for(int i=0;i<n;i++) 72                 if(ts.mark[i*2]) printf("C/n"); 73                 else { 74                     if(a[i]*n<x) printf("B/n"); 75                     else printf("A/n"); 76                 } 77     } 78     return 0; 79 }

正文到此结束