UVAlive 3211 Now or Later

题目大意：

有n架飞机需要着陆。每架飞机都可以选择”早着陆“和”晚着陆“两种方式之一，且必须选择一种。第i架飞机的早着陆时间为Ei，晚着陆时间为Li，不得在其他时间着陆。你的任务是为这些飞机安排着陆方式，是的整个着陆计划尽量安全。换句话说，如果把所有飞机的师姐着陆时间按照从早到晚的顺序排列，相邻两个着陆时间间隔的最小值（称为安全间隔）应尽量大。

题目链接：http://vjudge.net/problem/viewProblem.action?id=33799

思路：

利用2-SAT+二分，不断去找中值，将它代入2-SAT图中来进行判断这个值能否使每台飞机都能成功安排时间起飞

这里的二分函数：

bool findMid(int mid)
{
    init();
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            for(int k=i+1;k<n;k++){
                for(int t=0;t<2;t++)
                    if(abs(time[i][j]-time[k][t])<mid){
                        add_clause(i,j^1,k,t^1);
                    }
            }
        }
    }
    return solve();
}

把所有能够建立关系的点连成有向图，然后通过这个图来进行判断

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 2005*2
#define max(a,b) a>b?a:b
int c,S[N],time[2005][2],n;
bool mark[N];
vector<int> G[N];
int abs(int a){
    return a>0?a:-a;
}
bool dfs(int u)
{
    if(mark[u^1]) return false;
    if(mark[u]) return true;
    mark[u]=true;
    S[c++]=u;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(!dfs(v)) return false;
    }
    return true;
}
void init()
{
    for(int i=0;i<N;i++) G[i].clear();
    memset(mark,false,sizeof(mark));
    memset(S,0,sizeof(S));
    c=0;
}
void add_clause(int i,int a,int j,int b)
{
    int m=2*i+a;
    int n=2*j+b;
    G[m^1].push_back(n);
    G[n^1].push_back(m);
}
bool solve()
{
    for(int i=0;i<N;i+=2){
        if(!mark[i]&&!mark[i^1]){
            if(!dfs(i)){
                while(c>0) mark[S[--c]]=0;
                if(!dfs(i^1)) return false;
            }
        }
    }
    return true;
}
bool findMid(int mid)
{
    init();
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            for(int k=i+1;k<n;k++){
                for(int t=0;t<2;t++)
                    if(abs(time[i][j]-time[k][t])<mid){
                        add_clause(i,j^1,k,t^1);
                    }
            }
        }
    }
    return solve();
}
int main()
{
    int maxn=0;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d%d",&time[i][0],&time[i][1]);
            maxn=max(maxn,time[i][0]);
            maxn=max(maxn,time[i][1]);
        }
        int st=0,la=maxn,mid,ans;
        while(st<=la){
            mid=(st+la)/2;
            if(findMid(mid)) ans=mid,st=mid+1;
            else la=mid-1;
        }
        printf("%d
",ans);
    }

    return 0;
}