首页 > 代码库 > UVa 1391 Astronauts （2SAT）
UVa 1391 Astronauts （2SAT）
题意：给出一些宇航员他们的年龄，x是他们的平均年龄，其中A任务只能给年龄大于等于x的人，B任务只能给小于x的人，C任务没有限制。再给出m对人，他们不能同任务。现在要你输出一组符合要求的任务安排。
思路：2SAT。
设Ai表示第i个人的任务，如果i的年龄大于等于x，那么Ai=true表示分到A任务，flase表示分到C任务。如果i年龄小于x则Ai=true表示分到B任务，flase表示分到C任务。
考虑对于这m对里的每对人，如果他们是同组的，那么（Ai并非Aj）或（非Ai并Aj）等价于 （非Ai或非Aj）并（Ai或Aj）
如果他们是不同组的，那么只要他们都不是C任务就行，即非（非Ai并非Aj）等价于（Ai或Aj）
这样就可以用2SAT做了。注意平均年龄x要用浮点数。
我用的是LRJ的模板，2i表示Ai=false，2i+1表示Ai=true
#include <cstdio>#include <cmath>#include <vector>#include <cstring>using namespace std;const int maxn =100005;struct TwoSAT{ int n; vector<int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2],c; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x]=true; S[c++]=x; for(int i=0; i<G[x].size(); ++i) if(!dfs(G[x][i])) return false; return true; } void init(int n) { this->n=n; for(int i=0; i<n*2; ++i) G[i].clear(); memset(mark,0,sizeof(mark)); } void add_clause(int x,int xval,int y,int yval) { x=x*2+xval; y=y*2+yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve() { for(int i=0; i<n*2; i+=2) { if(!mark[i]&&!mark[i+1]) { c=0; if(!dfs(i)) { while(c>0) mark[S[--c]]=false; if(!dfs(i+1)) return false; } } } return true; }};TwoSAT solver;int age[100005];int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(!n&&!m) break; double x=0; for(int i=0; i<n; ++i) { scanf("%d",&age[i]); x+=age[i]; } x/=n; solver.init(n); for(int i=0; i<m; ++i) { int a,b; scanf("%d%d",&a,&b); a--; b--; if((age[a]>=x&&age[b]>=x)||(age[a]<x&&age[b]<x)) { solver.add_clause(a,0,b,0); solver.add_clause(a,1,b,1); } else solver.add_clause(a,1,b,1); } if(!solver.solve()) puts("No solution."); else { for(int i=0; i<2*n; i+=2) if(solver.mark[i]) printf("C\n"); else printf("%c\n",age[i/2]>=x?‘A‘:‘B‘); } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。