题解 UVA1146 【Now or later】（2-SAT）

一看就是一道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是否可行 代码如下 ```cpp #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; } ```