算法：UVa 1146 - Now or later（2-SAT + 二分）

算法：UVa 1146 - Now or later（2-SAT + 二分）2014-01-10 csdn shuangde800【题目大意】

有n架飞机要着陆，每架飞机都可以选择“早着陆”或者“晚着陆”中的一种，不能在其他时间着陆。给出每架飞机“早着陆”和“玩着陆”的时间，问怎样安排着陆，才可以使得着任意两架飞机的陆时间间隔最小，输出最小值。

【思路】

水题，二分最小间隔时间，用2-SAT判断。

【代码】

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<cmath>using namespace std;const int MAXN = 2005;const int VN = MAXN*2;const int EN = MAXN*MAXN*4;int n, m;int t[MAXN][2];struct Graph{int size, head[VN];struct{int v, next; }E[EN];void init（）{size=0; memset（head, -1, sizeof（head））;}void addEdge（int u, int v）{E[size].v = v;E[size].next = head[u];head[u] = size++;}}g;class Two_Sat{public:bool check（）{scc（）;for（int i=0; i<n; ++i）if（belong[i] == belong[i+n]）return false;return true;}private:void tarjan（const int u）{int v;low[u] = dfn[u] = ++idx;instack[u] = true;sta[top++] = u;for（int e=g.head[u]; e！=-1; e=g.E[e].next）{v = g.E[e].v;if（dfn[v] == -1）{tarjan（v）;low[u] = min（low[u], low[v]）;}else if（instack[v]）low[u] = min（low[u], dfn[v]）;}if（dfn[u] == low[u]）{++bcnt;do{v = sta[--top];instack[v] = false;belong[v] = bcnt;}while（u ！= v）;}}void scc（）{idx = top = bcnt = 0;memset（instack, 0, sizeof（instack））;memset（dfn, -1, sizeof（dfn））;for（int i=0; i<2*n; ++i）if（dfn[i] == -1）tarjan（i）;}private:int idx, top, bcnt;int sta[VN], low[VN], dfn[VN], belong[VN];bool instack[VN];}sat;void buildGraph（int minT）{g.init（）;for（int i=0; i<n; ++i）{for（int j=i+1; j<n; ++j）{int ta1=t[i][0], ta2=t[i][1];int tb1=t[j][0], tb2=t[j][1];if（abs（ta1-tb1） < minT）{g.addEdge（i, j+n）;g.addEdge（j, i+n）;}if（abs（ta1-tb2） < minT）{g.addEdge（i, j）;g.addEdge（j+n, i+n）;}if（abs（ta2-tb1） < minT）{g.addEdge（i+n, j+n）;g.addEdge（j, i）;}if（abs（ta2-tb2） < minT）{g.addEdge（i+n, j）;g.addEdge（j+n, i）;}}}}int main（）{while（~scanf（"%d", &n））{for（int i=0; i<n; ++i）scanf（"%d%d", &t[i][0], &t[i][1]）;int l=0, r=1e7, mid, ans=-1;while（l < r）{mid = （l+r）>>1;buildGraph（mid）;if（sat.check（））{ans = mid;l = mid+1;}elser = mid;}printf（"%d
", ans）;}return 0;}