洛谷题目传送门
题目描述
有n架飞机需要着陆。每架飞机都可以选择“早着陆”和“晚着陆”两种方式之一，且必须选择一种。第i架飞机的早着陆时间为Ei，晚着陆时间为Li，不得在其他时间着陆。你的任务是为这些飞机安排着陆方式，使得整个着陆计划尽量安全。换句话说，如果把所有飞机的实际着陆时间按照从早到晚的顺序排列，相邻两个着陆时间间隔的最值（称为安全间隔）应尽量大。
输入格式
输入包含若干组数据。每组数据第一行为飞机的数目n。以下n行每行两个整数，即早着陆时间和晚着陆时间。所有时间t 满足0<=t<=10^7。输入结束标志为文件结束符（EOF）。
输出格式
对于每组数据，输出安全间隔的最大值。（记得换行)
输入输出样例
说明/提示
n <= 2000; 剩下的所有数据保证不超过int范围
首先，从题目的要求来看，xxxx尽量大，xxxx尽量小，一般这种要求我们可以考虑二分查找答案。（套路）
于是，题目就成了判定：是否能使相邻的着陆时间不小于P，即我们目前二分枚举的时间。
继续看题，每种飞机有两种着陆方式：早着陆和晚着陆，考虑分别用0和1表示。
对于这种含有“或”的题，考虑用2—SAT问题进行求解。
建图：
每一个节点v表示一种选择，一架飞机我们可以拆成两个点：早 与 晚。
枚举每架飞机和它后面飞机的情况：如果两个时间相差小于P，则连边，表明选择第一种情况就必须选择第二种情况。（在枚举的时候应用for循环从小到大，优先早着陆，尽量贴近P，防止浪费时间）。
跑图：
建好图之后，要做的就是跑图了。如何跑？当然是直接套用2—SAT问题的模板：用Tarjan强联通算法.
如建图中所说，我们的‘边’代表的是必须选择。那么，如果我们选择一架飞机的“0”，然后经过一系列传导，又必须选择‘1’，怎么办？（凉拌）
如果出现这种情况，自相矛盾，那么，原问题肯定无解！！！
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + ; struct edge{
int u,v,next;
}e[maxn << ];
//全部开两倍！！！有两倍的点
int f[maxn << ],low[maxn << ],dfn[maxn << ];
int scc[maxn << ];
bool vis[maxn << ];
int n,cac,cnt,m,top;
stack <int> stack1;
int T[maxn][]; void clean(){//不要被吓到了
for(int i = ;i <= * n; i++){
f[i] = dfn[i] = ;
}
cac = ;
top = ;
return;
} int jueduizhi(int x){
if(x < )x = -x;
return x;
} //-------------------------以下才是重点 void add(int u,int v){
top++;
e[top].u = u;//这个点(起点)
e[top].v = v;//它连向的那个点(终点)
e[top].next = f[u];
f[u] = top;
return;
} void tarjan(int now){
low[now] = dfn[now] = ++cac;//初始化用的
stack1.push(now);
vis[now] = ;
for(int i = f[now]; i ; i = e[i].next){
int v = e[i].v;//有连边
if(!dfn[v]){
tarjan(v);
low[now] = min(low[now],low[v]);
}else if(vis[v])
low[now] = min(low[now],dfn[v]);
}
if(low[now] == dfn[now]){
int cur;
cnt++;//是第几个强连通 ??
do{
cur = stack1.top();
stack1.pop();
vis[cur] = ;
scc[cur] = cnt;//记录每个点所在的强连通
}while(now != cur);
}
} bool two_SAT(){
for(int i = ; i <= * n; i++)
if(!dfn[i] )
tarjan(i);//tarjan找强连通分量
for(int i = ; i <= n; i++)
if(scc[i] == scc[i + n])return ;
//a条件和非a条件在同一个强连通分量，原问题无解
return ;
} bool test(int diff){
clean();
for(int i = ;i <= n; i++)//枚举每架飞机
for(int aval = ;aval < ; aval++)//早还是晚?
for(int j = i + ;j <= n; j++)//往下枚举后面的飞机
for(int bvbl = ;bvbl < ; bvbl++){//一样，分两种情况
if(jueduizhi(T[i][aval] - T[j][bvbl]) < diff){
int a = i,b = j;
int nota = aval ^ ,notb = bvbl ^ ;
add(a + nota * n,b + bvbl * n);
add(b + notb * n,a + aval * n);
}
}
return two_SAT();
} int main(){
// freopen("hh.txt","r",stdin);
while(scanf("%d",&n) != EOF && n){
int l = ,r = ;
for(int i = ;i <= n; i++)
for(int a = ;a < ; a++){
scanf("%d",&T[i][a]);
r = max(r,T[i][a]);
}
while(l < r){
int mid = l + (r - l + ) / ;//必须向上取整，不然全部爆0
//int mid = l + r >> 1;
if(test(mid)) l = mid;
else r = mid - ;
}
printf("%d\n",l);
}
return ;
}
luogu那道题是自己手打上传的，数据可能有点毒瘤。。。