照这书写的。。(┬＿┬)
这个题找bug找了半天原来是#define MAXN 2000+20不行。。怪我没看FQA。。哎。。然后改成#define MAXN 2020就行了
这题是2-sat模型。。。虽然我也不知道为什么要这么做。但是好歹写了有个2-sat模版吧
2-sat:有n个布尔变量xi，另有m个需要满足的条件，每个条件的形式都是“xi为真/假或者xj为真/假”。比如：“x1为真或者x2为假”。这里或者是指两个条件至少有一个是正确的，这样有三种组合满足。
做法：我们将一个点拆成两个点，2i和2i+1,分别表示真或假
对“xi为真或者xj为真”这样的条件，我们连一条有向边2i+1--->2j.表示当xi为假时，xj要为真。同理还需要一条边2j+1--->2i，表示xj为假时，xi要为真。每个条件对应两条“对称”的边。
接下来考虑每个没有被赋值的变量，设为xi。我们先假定他为真，标识2i,并沿着有向边标识所有能标识的点，如果标识过程中发现某个变量对应的两个点都被标识了，说明“xi为真”这个假设不成立，需要改为‘xi为假’，然后重新标识，若还是不成立，则这个2-sat问题无解。
View Code
#include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include <stack> using namespace std; #define MAXN 2020 //被坑死了 int n,T[MAXN][2]; struct TwoSAT{ int n; vector<int>G[MAXN*2]; bool mark[MAXN*2]; stack<int>S; bool dfs(int x) { if(mark[x^1])return false; if(mark[x])return true; mark[x]=true; S.push(x); for(int i=0;i<G[x].size();i++) { int v=G[x][i]; if(!dfs(v))return false; } return true; } void init(int _n) { n=_n; for(int i=0;i<2*n;i++) G[i].clear(); memset(mark,0,sizeof(mark)); } void add_clause(int x,int xval,int y,int yval) { x=x*2+xval; y=y*2+yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve() { for(int i=0;i<2*n;i=i+2) { if(!mark[i]&&!mark[i+1]){ while(!S.empty()) { S.pop(); } if(!dfs(i)) { while(!S.empty()) { mark[S.top()]=false; S.pop(); } if(!dfs(i+1))return false; } } } // for(int i=0;i<2*n;i++) // if(mark[i])printf("%d ",T[i/2][i%2]); // printf("\n"); return true; } }; bool test(int diff) { TwoSAT solver; 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_clause(i,a^1,j,b^1); return solver.solve(); } int main(){ // freopen("in.txt","r",stdin); while(scanf("%d",&n)==1) { int L=0,R=0; for(int i=0;i<n;i++) for(int a=0;a<2;a++) { scanf("%d",&T[i][a]); R=max(R,T[i][a]); } while(L<R) { int mid=L+(R-L+1)/2; if(test(mid))L=mid; else R=mid-1; } printf("%d\n",L); } return 0; }