算法：UVa 1146

【题目大意】

有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;
            }else
                r = mid;
        }
        printf("%d\n", ans);
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， 时间
， head
， size
， 最小
1146
mysql 1146、mysql 1146错误、qt1146、1146年、1147，以便于您获取更多的相关知识。