2-sat 问题【例题 Flags（2-sat+线段树优化建图）】

序：

模拟赛考了一道 2-sat 问题。之前从来没听过……

考完才发现其实这个东东只要一个小小的 tarjan 求强连通分量就搞定了。

这个方法真是巧妙啊，拿来讲讲。

What is it？ [・_・？]

这个算法是为了应对一些这样的条件：x1 与 x1 中至少有一个成立

算法：

既然是“2"-sat，那就要充分发挥 “two” 的优势，由于x1限制关系，有一些点我们选了后，有一些点就不能选了，那我们就只能选另一个点了满足 x2。

我们把 a 想它必须选的点 b 连有向边，这样就构成了一个图，判定的话，判断是否有两个不能同时存在的点在一个强连通分量中就好了！

这有一位大佬写的比我更好 OTZ

当然重点是讲模拟赛的题！

例题 Flags：

传送门

题目大意：数轴上有 n 个旗子，第 i 个可以插在坐标 xi 或者 yi，最大化两两旗子之间的最小距离。

题解：

我们可以二分答案，转化为一个 2-sat 问题。

二分最小距离 d，那么一个点 a 向左向右 d 的 b 点都不能选，那么选了 a 就必须选 b 的另一个位置，然后我们连边，最后判断是不是有一个点的两个位置是不是在一个强连通分量里，在则不能，否则可以。

这题还有一个点就是如果直接建边的话，就有 $n^2$ 条边，你会发现这题一个点的连边都是连续的，那就不妨线段树优化建图。具体思想戳这里。

CODE：

 #include<iostream>

 #include<cstdio>

 #include<stack>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int v[];

 int n,x,y,tot=,h[];

 int scc[],dfn[],low[],C,cnt;

 bool vis[];

 struct Edge{

     int x,next;

 }e[];

 pair<int,int> a[];

 stack<int> s;

 inline void add_edge(int x,int y){

     e[++tot].x=y;

     e[tot].next=h[x],h[x]=tot;

 }

 void tarjan(int x){

     dfn[x]=low[x]=++cnt;

     s.push(x),vis[x]=true;

     for(int i=h[x];~i;i=e[i].next){

         if(!dfn[e[i].x]){

             tarjan(e[i].x),low[x]=min(low[x],low[e[i].x]);

         }else if(vis[e[i].x]){

             low[x]=min(low[x],dfn[e[i].x]);

         }

     }

     if(dfn[x]==low[x]){

         C++;

         int tmp;

         for(;;){

             tmp=s.top();

             vis[tmp]=false,scc[tmp]=C;

             s.pop();

             if(tmp==x)break;

         }

     }

 }

 void build(int o,int l,int r){

     if(r-l==){

         add_edge(o+n*,a[l].second^);

         return;

     }

     add_edge(o+n*,(o<<)+n*);

     add_edge(o+n*,(o<<|)+n*);

     int mid=l+r>>;

     build(o<<,l,mid),build(o<<|,mid,r);

 }

 void link(int o,int l,int r,int x,int y,int a){

     if(l>=x&&r<=y){

         add_edge(a,o+n*);

         return;

     }

     int mid=l+r>>;

     if(x<mid)link(o<<,l,mid,x,y,a);

     if(y>mid)link(o<<|,mid,r,x,y,a);

 }

 inline pair<int,int> get(int x,int len){

     int l=,r=x;

     pair<int,int> ans;

     while(l<r){

         int mid=l+r>>;

         if(a[x].first-a[mid].first<len)r=mid;

         else l=mid+;

     }

     ans.first=l;

     l=x,r=n*-;

     while(l<r){

         int mid=l+r+>>;

         if(a[mid].first-a[x].first<len)l=mid;

         else r=mid-;

     }

     ans.second=l;

     return ans;

 }

 inline bool check(int d){

     memset(scc,,sizeof(scc));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     memset(h,-,sizeof(h)),tot=;

     build(,,n*);

     for(int i=;i<n*;i++){

         int id=a[i].second;

         pair<int,int> x=get(i,d);

         if(i<x.second)link(,,n*,i+,x.second+,id);

         if(x.first<i)link(,,n*,x.first,i,id);

     }

     C=cnt=;

     for(int i=;i<n*;i++)if(!dfn[i])tarjan(i);

     for(int i=;i<n*;i++)

         if(scc[a[i].second]==scc[a[i].second^])return false;

     return true;

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<n;i++){

         scanf("%d%d",&x,&y);

         a[*i+]=make_pair(x,*i+);

         a[*i]=make_pair(y,*i);

     }

     sort(a,a+n*);

     int l=,r=;

     while(l<r){

         int mid=l+r+>>;

         if(check(mid))l=mid;

         else r=mid-;

     }

     printf("%d",l);

 }

巴特西

2-sat 问题【例题 Flags（2-sat+线段树优化建图）】

序：

What is it？ [・_・？]

算法：

例题 Flags：

题解：

CODE：

最新文章

热门文章

巴特西

2-sat 问题 【例题 Flags（2-sat+线段树优化建图）】

序：

What is it？ [・_・？]

算法：

例题 Flags：

题解：

CODE：

最新文章

热门文章

2-sat 问题【例题 Flags（2-sat+线段树优化建图）】