训练指南 UVALive - 3211 （2-SAT + 二分）

Diposting di | Edited on

Now or later

UVALive - 3211

题意

n架飞机，每架可选择两个着落时间。安排一个着陆时间表，使得着陆间隔的最小值最大

题解

二分查找最大值P，每次都用2—SAT判断是否可行。

假设A早和B早的时间会冲突，那么我们就要规定，A晚或者B晚，规定其中一个必须要晚，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct TwoSAT{
    int n;
    vector<int> G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2],c;

    bool dfs(int x){
        if(mark[x^1])return false;
        if(mark[x])return true;
        mark[x]=true;
        S[c++]=x;
        for(int i=0;i<G[x].size();i++)
            if(!dfs(G[x][i]))return false;
        return true;
    }

    void init(int n){
        this->n=n;
        for(int i=0;i<n*2;i++)G[i].clear();
        memset(mark,0,sizeof(mark));
    }
    /// x=xval or y= yval;
    void add_caluse(int x,int xval,int y,int yval){
        x=x*2+xval;
        y=y*2+yval;
        G[x^1].push_back(y);///如果x为真 那么y必须为假;
        G[y^1].push_back(x);///如果y为真 那么x必须为假;
    }

    bool solve(){
        for(int i=0;i<n*2;i+=2)
        if(!mark[i]&&!mark[i+1]){
            c=0;
            if(!dfs(i)){
                while(c>0)mark[S[--c]]=false;
                if(!dfs(i+1))return false;
            }
        }
        return true;
    }
};
int n,T[maxn][2];
TwoSAT solver;

bool test(int diff){
    solver.init(n);
    for(int i=0;i<n;i++)for(int a=0;a<2;a++)
        for(int j=i+1;j<n;j++)for(int b=0;b<2;b++)
        if(abs(T[i][a]-T[j][b])<diff)solver.add_caluse(i,a^1,j,b^1);
    return solver.solve();
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin>>n&&n){
        int L=0,R=0;
        for(int i=0;i<n;i++)for(int a=0;a<2;a++){
            cin>>T[i][a];
            R=max(T[i][a],R);
        }
        int ans=0;
        while(L<=R){
            int mid=(L+R)/2;
            if(test(mid)){
                ans=mid;
                L=mid+1;
            }
            else R=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}