uva 1146 Now or late （暴力2-SAT）

/*
裸地2-SAT问题 关键是模型转化
最小的最大 显然二分 关键是Judge的时候怎么判断
每个航班是早是晚直接影响判断
早晚只能选一个 如果我们定义bool变量xi表示 i航班是否早到
每个航班虚拟出两个点2*i 2*i+1 分别表示是否早到 
然后就可以假设某个航班早到然后推导出一定连得某些边 
然后就开始选点 尝试这个点选不选 看看最后是否合法
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 4400
using namespace std;
int n,l,r,g[maxn][3],f[maxn],ans,c,s[maxn];
vector<int>G[maxn];
int Abs(int a)
{
    return a<0?-a:a;
}
void Add(int x,int y)
{
    G[x^1].push_back(y);G[y^1].push_back(x);
}
bool Dfs(int x)
{
    if(f[x^1])return 0;if(f[x])return 1;
    f[x]=1;s[c++]=x;
    for(int i=0;i<G[x].size();i++)
      if(!Dfs(G[x][i]))return 0;
    return 1;
}
bool Solve()//选点 
{
    for(int i=0;i<n*2;i+=2)
      {
          if(f[i]||f[i+1])continue;c=0;//表示同一航班的两个点只选一个 
        if(!Dfs(i))
          {
            while(c>0)f[s[--c]]=0;//撤销 
            if(!Dfs(i+1))return 0;
          }
      }
    return 1;
}
bool Judge(int x)
{
    for(int i=0;i<n*2;i++)G[i].clear();
    memset(f,0,sizeof(f));
    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(g[i][a]-g[j][b])<x)
        //i*2+a 不能和 j*2+b 同时选  那就i*2+a连j*2+(b^1)  j*2+b连i*2+(a^1)                                 
          Add(i*2+(a^1),j*2+(b^1));
    return Solve();
}
int main()
{
    while(scanf("%d",&n)==1&&n)
      {
          l=r=ans=0;
          for(int i=0;i<n;i++)
            for(int j=0;j<2;j++)
              {
                scanf("%d",&g[i][j]);
                r=max(r,g[i][j]);
            }
          while(l<=r)
            {
                int mid=(l+r)/2;
                if(Judge(mid))
                  {
                      ans=mid;l=mid+1;
              }
            else r=mid-1;
          }
        printf("%d
",ans);
      }
    return 0;
}
uva 1146 Now or late （暴力2-SAT）

相关推荐
