首页 > 代码库 > LA 3211 飞机调度（2—SAT）
LA 3211 飞机调度（2—SAT）
https://vjudge.net/problem/UVALive-3211
题意：
有n架飞机需要着陆，每架飞机都可以选择“早着陆”和“晚着陆”两种方式之一，且必须选择一种，第i架飞机的早着陆时间为E，晚着陆时间为L，不得在其他时间着陆。你的任务是为这些飞机安排着陆方式，使得整个着陆计划尽量安全。换句话说，如果把所有飞机的实际着陆时间按照从早到晚的顺序排列，相邻两个着陆时间间隔的最小值。
思路：
二分查找最大值P，每次都用2—SAT判断是否可行。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 using namespace std; 11 12 const int maxn=2000+5; 13 14 int T[maxn][2]; 15 16 struct TwoSAT 17 { 18 int n; 19 vector<int> G[2*maxn]; 20 bool mark[2*maxn]; 21 int S[2*maxn],c; 22 23 bool dfs(int x) 24 { 25 if(mark[x^1]) return false; 26 if(mark[x]) return true; 27 mark[x]=true; 28 S[c++]=x; 29 for(int i=0;i<G[x].size();i++) 30 if(!dfs(G[x][i])) return false; 31 return true; 32 } 33 34 void init(int n) 35 { 36 this->n=n; 37 for(int i=0;i<2*n;i++) G[i].clear(); 38 memset(mark,0,sizeof(mark)); 39 } 40 41 void add_clause(int x,int xval,int y,int yval) 42 { 43 x = x*2 + xval; 44 y = y*2 + yval; 45 G[x^1].push_back(y); 46 G[y^1].push_back(x); 47 } 48 49 bool solve() 50 { 51 for(int i=0;i<2*n;i+=2) 52 if(!mark[i] && !mark[i+1]) 53 { 54 c=0; 55 if(!dfs(i)) 56 { 57 while(c>0) mark[S[--c]]=false; 58 if(!dfs(i+1)) return false; 59 } 60 } 61 return true; 62 } 63 }solver; 64 65 bool test(int n,int p) 66 { 67 solver.init(n); 68 for(int i=0;i<n;i++) 69 for(int a=0;a<2;a++) 70 for(int j=i+1;j<n;j++) 71 for(int b=0;b<2;b++) 72 if(abs(T[i][a]-T[j][b])<p) solver.add_clause(i,a^1,j,b^1); 73 return solver.solve(); 74 } 75 76 int main() 77 { 78 //freopen("D:\\input.txt","r",stdin); 79 int n; 80 while(~scanf("%d",&n)) 81 { 82 int L=0,R=0; 83 for(int i=0;i<n;i++) 84 { 85 for(int a=0;a<2;a++) 86 { 87 scanf("%d",&T[i][a]); 88 R=max(R,T[i][a]); 89 } 90 } 91 while(L<=R) 92 { 93 int mid=(L+R)/2; 94 if(test(n,mid)) L=mid+1; 95 else R=mid-1; 96 } 97 printf("%d\n",R); 98 } 99 return 0;100 }
LA 3211 飞机调度（2—SAT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。