2-sat 问题学习小记 Poj 3207 Ikki's Story IV - Panda's Trick (可行性判定)

﹏ヽ暗。殇╰゛Y 2022-08-26 12:24 16阅读 0赞

2014-08-05更新

学习链接：

[伍昱 由对称性解2-sat问题（ppt）][_2-sat_ppt]

[【研究总结】2-sat问题 - JarjingX - 博客频道 - CSDN.NET][2-sat_ - JarjingX - _ - CSDN.NET]

[赵爽 2-sat解法浅析（pdf）][2-sat_pdf]

[2-SAT总结 - kuangbin - 博客园][2-SAT_ - kuangbin -]

[2-sat 相关问题总结 - BootStar - 博客频道 - CSDN.NET][2-sat _ - BootStar - _ - CSDN.NET]

模板和代码均参考了kuangbin大神的，他求强连通分量的方法用得是Kosaraju算法，这里有个对比分析：

[6.3.1 强连通分支算法--Kosaraju算法、Tarjan算法和Gabow算法 - lwee - 博客园][6.3.1 _--Kosaraju_Tarjan_Gabow_ - lwee -]

最近找了一个基于Tarjan的模板，就个人而言还是Tarjan比较熟练。

[图论\_\_2-SAT - D\_Double's Journey][2-SAT - D_Double_s Journey]

2014-08-31 更新

简单概述一下2-sat：

有n组元素，每组两个，从中选出n个，每组选且只选一个。  
这2n个元素中有些元素之间有矛盾关系，要求选出的n个元素中，任意两个之间都不存在矛盾。  
问是否存在满足条件的选取方案。这就是2-sat问题。  
解决方法如下，例如a,b一组，c,d一组，a,c有矛盾，那么选a则不能选c，不选c则必须选d。  
所以选a就必须选d。同理选c就必须选b。我们引两条边，a->d, c->b。对于所有的矛盾都用类似的方式加边。  
这样只要从x点可以走到y点，那么选x点就必须选y点。然后对全图求强连通分支。  
在一个强连通分支中，选了一个点，则必须选强连通分支中的所有点。  
如果有某两个点属于同一组，且属于同一个强连通分支，则必然无解，否则有解。

常见模型：

模型一：两者（A，B）不能同时取  
　　那么选择了A就只能选择B’，选择了B就只能选择A’  
　　连边A→B’，B→A’  
  
  
模型二：两者（A，B）不能同时不取  
　　那么选择了A’就只能选择B，选择了B’就只能选择A  
　　连边A’→B，B’→A  
  
  
模型三：两者（A，B）要么都取，要么都不取  
　　那么选择了A，就只能选择B，选择了B就只能选择A，选择了A’就只能选择B’，选择了B’就只能选择A’  
　　连边A→B，B→A，A’→B’，B’→A’  
  
  
模型四：两者（A，A’）必取A  
　　连边A’→A

本题算是2-sat问题的入门题，但稍有难度，建议练习一两道别的题再来做这道。

本题只要求判断可行性，不要求给出方案。

题意：平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只会连接的一条边。问能不能连接这m条边，使这些边都不相交。举个例子：比如1 5连边，2，6连边，由于点是顺序排列的，一画图就可以发现，这两条边必须一个从圆外面连，一个从内部连，否则就会相交。如果再加入3 7这条边，那么就必须相交了。

思路：可以转化成标准的2-sta问题：

1：每个边看成2个点：分别表示在内部连接和在外部连接，只能选择一个。计作点i和点i'

2：如果两条边i和j必须一个画在内部，一个画在外部那么连边：  
i->j’, 表示i画内部的话，j只能画外部，即j’  
j->i’，同理  
i’->j，同理  
j’->i，同理

先求原图的强连通分量，并缩点，判断是否存在(i,i')属于同一组，若存在，则不可能，若不存在则可能。

#include <queue>
    #include <vector>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=1005;
    
    bool visit[N];
    queue<int>q1,q2;
    
    vector<vector<int> >adj; //原图    //中间一定要加空格把两个'>'隔开
    vector<vector<int> >radj;//逆图
    vector<vector<int> >dag; //缩点后的逆向DAG图
    int n,cnt;
    
    int id[N],order[N],ind[N];//强连通分量,访问顺序,入度
    
    struct Node
    {
        int s,t;
    }node[N];
    
    void dfs (int u)
    {
    	visit[u]=true;
    	int len=adj[u].size();
    	for (int i=0;i<len;i++)
    		if (visit[adj[u][i]]==false)
    			dfs(adj[u][i]);
    	order[cnt++]=u;
    }
    
    void rdfs (int u)
    {
    	visit[u]=true;
    	id[u]=cnt;
    	int len=radj[u].size();
    	for (int i=0;i<len;i++)
    		if (visit[radj[u][i]]==false)
    			rdfs(radj[u][i]);
    }
    
    void Kosaraju () //求强连通分量并缩点
    {
    	int i;
    	memset(visit,false,sizeof(visit));
    	for (cnt=0,i=0;i<2*n;i++)
    		if (visit[i]==false)
    			dfs(i);
    	memset(id,0,sizeof(id));
    	memset(visit,false,sizeof(visit));
    	for (cnt=0,i=2*n-1;i>=0;i--)
    		if (visit[order[i]]==false)
    		{
    			cnt++;//这个一定要放前面来
    			rdfs(order[i]);
    		}
    }
    
    bool Solve ()
    {
    	for (int i=0;i<n;i++)
    		if (id[2*i]==id[2*i+1])
    			return false;
    	return true;
    }
    
    int main ()
    {
    	int x,y,i;
    	scanf("%*d%d",&n);
    	for (i=0;i<n;i++)
    	{
    		scanf("%d%d",&x,&y);
    		if (x>y) swap(x,y);
    		node[i].s=x;
    		node[i].t=y;
    	}
    	adj.assign(2*n,vector<int>());
    	radj.assign(2*n,vector<int>());
    	for (i=0;i<n;i++) for (int j=i+1;j<n;j++)
    		if ((node[i].s<node[j].s && node[j].s<node[i].t && node[i].t<node[j].t) || (node[j].s<node[i].s && node[i].s<node[j].t && node[j].t<node[i].t))
    		{
    			adj[2*i].push_back(2*j+1);  //i-j'
    			adj[2*j+1].push_back(2*i);  //j'-i
    			adj[2*i+1].push_back(2*j);  //i'-j
    			adj[2*j].push_back(2*i+1);  //j-i'
    			radj[2*j+1].push_back(2*i);
    			radj[2*i].push_back(2*j+1);
    			radj[2*j].push_back(2*i+1);
    			radj[2*i+1].push_back(2*j);
    		}
    	Kosaraju();
    	if (Solve())
    		printf("panda is telling the truth...\n");
    	else printf("the evil panda is lying again\n");
    	return 0;
    }

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int MAXN = 1010;  
    const int VN   = MAXN*2;  
    const int EN   = VN*VN/2;  
    int n,m;  
    int arr[VN][2];
    
    struct Edge{
    	int v, next;
    };
    
    class Graph{
    public:
    	int head[VN],size;
    	Edge E[EN];
    	void init(){
    		size = 0;
    		memset(head, -1, sizeof(head));
    	}
    	void Add (int u,int v){
    		E[size].v = v;
    		E[size].next = head[u];
    		head[u] = size++;
    	}
    }g;
    
    class Two_Sat{
    public:
    	bool Check(const Graph&g, const int n){
    		SCC(g,n);
    		for (int i=0;i<n;i++)
    			if (belong[i*2] == belong[i*2+1])
    				return false;
    		return true;
    	}
    private:
    	int top, bcnt, idx;
    	int sta[VN],belong[VN];
    	int dfn[VN],low[VN];
    	bool inStack[VN];
    	
    	void targan (const Graph&g, const int u){
    		int v;
    		dfn[u] = low[u] = ++idx;
    		sta[top++] = u;
    		inStack[u] = true;
    		
    		for (int i=g.head[u]; i!=-1; i=g.E[i].next){
    			v = g.E[i].v;
    			if (dfn[v] < 0){
    				targan(g, v);
    				low[u] = min(low[u], low[v]);
    			}
    			else if(inStack[v])
    				low[u] = min(low[u], dfn[v]);
    		}
    		
    		if (dfn[u] == low[u]){
    			++bcnt;
    			do{
    				v = sta[--top];
    				inStack[v] = false;
    				belong[v] = bcnt;
    			}while(u != v);
    		}
    	}
    
    	void SCC (const Graph&g, int n){
    		top=bcnt=idx=0;
    		memset(dfn,-1,sizeof(dfn));
    		memset(low,0,sizeof(low));
    		memset(belong,0,sizeof(belong));
    		memset(inStack,false,sizeof(inStack));
    		for (int i=0; i<2*n;i++)
    			if (dfn[i] < 0) targan(g,i);
    	}
    }sat;
    
    bool isCross (int* A, int *B){
    	return  A[0]>B[0] && A[0]<B[1] && A[1]>B[1]
    		|| A[1]>B[0] && A[1]<B[1] && A[0]<B[0];
    }
    
    int main ()
    {
    	int i;
    	scanf("%d%d",&n,&m);
    	g.init();
    	for (i=0;i<m;i++)
    	{
    		scanf("%d%d", &arr[i][0], &arr[i][1]);  
    		if (arr[i][0] > arr[i][1])
    			swap(arr[i][0], arr[i][1]);
    	}
    	for (i=0;i<n;i++)
    		for (int j=i+1;j<n;j++)
    			if (isCross(arr[i], arr[j]))
    			{
    				int u=i*2;
    				int v=j*2;
    				g.Add(u,v^1);
    				g.Add(u^1,v);
    				g.Add(v,u^1);
    				g.Add(v^1,u);
    			}
    	if (sat.Check(g,n))
    		puts("panda is telling the truth...");
    	else puts("the evil panda is lying again");
    	return 0;
    }

[_2-sat_ppt]: http://wenku.baidu.com/view/afd6c436a32d7375a41780f2.html
[2-sat_ - JarjingX - _ - CSDN.NET]: http://blog.csdn.net/jarjingx/article/details/8521690
[2-sat_pdf]: http://wenku.baidu.com/view/0f96c3daa58da0116c1749bc.html
[2-SAT_ - kuangbin -]: http://www.cnblogs.com/kuangbin/archive/2012/10/05/2712429.html
[2-sat _ - BootStar - _ - CSDN.NET]: http://blog.csdn.net/sprithy_dream/article/details/8116640
[6.3.1 _--Kosaraju_Tarjan_Gabow_ - lwee -]: http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591370.html
[2-SAT - D_Double_s Journey]: http://blog.csdn.net/shuangde800/article/category/1408597