uva 1146(2-SAT+二分判断)

题意：有n架飞机需要着陆，每架飞机都有两个时间可以选择，早和晚。告诉你每架飞机的这两个时间，然后我们定义相邻两架飞机着陆时间间隔的最小值为安全间隔。问你安全间隔最大能为多少。

思路：一个典型的2-sat+二分判断的问题。首先我们对安全间隔二分答案，然后再2-sat判断可行性。思路理清的话没什么难度。

代码如下：

  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-02-01 12:12
  5  * Filename     : uva_1146.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 = 10020;
 34 vector<int> Map[LEN], rMap[LEN], vs;
 35 int n, vis[LEN], tim[LEN][2], sccn[LEN];
 36 
 37 int abs(int a){
 38      return a>0?a:-a;
 39 }
 40 
 41 void dfs(int v){
 42     vis[v] = 1;
 43     for(int i=0; i<Map[v].size(); i++)
 44        if(!vis[Map[v][i]])dfs(Map[v][i]);
 45     vs.PB(v);
 46 }
 47  
 48 void rdfs(int v, int f){
 49     vis[v] = 1;
 50     sccn[v] = f;
 51     for(int i=0; i<rMap[v].size(); i++)
 52         if(!vis[rMap[v][i]]) rdfs(rMap[v][i], f);
 53 }
 54 
 55 int scc()
 56 {
 57      memset(vis, 0, sizeof vis);
 58      vs.clear();
 59      for(int i=0; i<n*2; i++) if(!vis[i])dfs(i);
 60      memset(vis, 0, sizeof vis);
 61      int k = 0;
 62      for(int i=vs.size()-1; i>=0; i--)if(!vis[vs[i]])rdfs(vs[i], k++);
 63      return k;
 64 }
 65 
 66 void addedge(int a, int b){
 67     Map[a].PB(b);
 68     rMap[b].PB(a);
 69 }
 70 
 71 bool Judge(int bak){
 72     for(int i=0; i<LEN; i++) Map[i].clear();
 73     for(int i=0; i<LEN; i++) rMap[i].clear();
 74      for(int i=0; i<n; i++)
 75         for(int j=0; j<n; j++){
 76             if(i == j) continue;
 77             int a = i*2, fa = i*2+1, b = j*2, fb = j*2+1;
 78             if(abs(tim[i][0]-tim[j][0]) < bak){
 79                 addedge(a, fb);
 80                 addedge(b, fa);        
 81             }
 82             if(abs(tim[i][0]-tim[j][1]) < bak){
 83                 addedge(a, b);
 84                 addedge(fb, fa);
 85             }
 86             if(abs(tim[i][1]-tim[j][0]) < bak){
 87                 addedge(fa, fb);
 88                 addedge(b, a);
 89             }
 90             if(abs(tim[i][1]-tim[j][1]) < bak){
 91                 addedge(fb, a);
 92                 addedge(fa, b);
 93             }
 94         }
 95     scc();
 96     for(int i=0; i<n*2; i+=2)
 97         if(sccn[i] == sccn[i+1]) return false;
 98     return true;
 99 }
100 
101 int main()
102 {
103 //    freopen("in.txt", "r", stdin);
104 
105     while(scanf("%d", &n)!=EOF){
106         for(int i=0; i<n; i++)
107             scanf("%d%d", &tim[i][0], &tim[i][1]);
108         int l = 0, r = 10000000;
109         while(l<r){
110             int mid = (l+r+1)/2;
111             if(Judge(mid))l = mid;
112             else r = mid-1;
113         }
114         printf("%d
", l);
115     }
116     return 0;
117 }

View Code

奔跑吧！少年！趁着你还年轻