题解 UVA1146 【Now or later】(2-SAT)

2018-05-05 14:37:35


一看就是一道2-SAT的题目,通过二分求出答案,通过2-SAT来检验是否可行

假设我们现在二分出安全时间为t,枚举出两架飞机i,j。i1是i飞机早着陆的时间,i2是晚着陆的时间,j1,j2同理。则如果abs(i1-j1)<t这两架飞机就无法都选择先降落,所以我们将i1->j2连一条边,j1->i2连一条边,表示选i1必须选j2,选j1就必须选i2,连完以后,我们检验是否存在矛盾情况,即一架飞机的两个降落时间都必须选就能判断当前的t是否可行

代码如下

#include<cstdio> 
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,cnt=0,p=0;
int a[2*2010],f[2*2010],s[2*2010];
int head[2*2010*2010],nxt[2*2010*2010],to[2*2010*2010];
void addedge(int x,int y)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
bool dfs(int x)
{
    int v;
    if(x%2==0) v=x-1;
    else v=x+1;
    if(f[x]) return 1;
    if(f[v]) return 0;
    f[x]=1;
    s[++p]=x;
    for(int i=head[x];i!=-1;i=nxt[i])
        if(!dfs(to[i])) return 0;
    return 1;
}
bool judge()//判断是否可行
{
    for(int i=1;i<2*n;i+=2)
        if(!f[i] && !f[i+1])
        {
            p=0;
            if(!dfs(i))
            {
                while(p>0) f[s[p--]]=0;
                if(!dfs(i+1)) return 0;//如果这架飞机两个时间都不行,就不行
            }
        }
    return 1;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int l=0,r=0;
        for(int i=1;i<n*2;i+=2)
            scanf("%d%d",&a[i],&a[i+1]),r=max(r,a[i+1]);
        while(l<=r)
        {
            cnt=0;
            memset(f,0,sizeof(f));
            memset(head,-1,sizeof(head));
            int mid=(l+r)/2;//二分t
            for(int i=1;i<=n*2;i++)
                for(int j=i+i%2+1;j<=n*2;j++)//如上文描述进行连边
                    if(abs(a[i]-a[j])<mid)
                    {
                        int u,v;
                        if(i%2==0) u=i-1;
                        else u=i+1;
                        if(j%2==0) v=j-1;
                        else v=j+1; 
                        addedge(i,v),addedge(j,u);
                    }
            if(judge()) l=mid+1;
            else r=mid-1;
        }
        cout<<l-1<<endl;
    }
    return 0;
}