POJ 3207 2SAT入门

本文主要是介绍POJ 3207 2SAT入门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题敲了好久，第一道入门题，还是看了别人的才懂的……

题意：有n个结点在圆上，然后有m条边把这些结点连起来，可以在圆内连，也可以在圆外连接。然后题目求的就是能否得出一个方案，就是连接的没有相交的……

思路：这入门题可以一眼就可以看出是2SAT问题了。设一结点 i ，然后2*i 为在圆内连接，2*i+1为在圆外连接；然后设另一结点为 j，然后2*j 为在圆内连接，2*j+1为在圆外连接；根据2SAT原理，2*i与2*j+1连双向边，2*j 与2*i+1连双向边，然后用tarjan求强连通，再判断这个结点i，是不是在圆内与在圆外都同时被选择连接了，然后同时被选择就是在同一个强连通里，说明不管在圆内还是圆外，不管怎么连接，都会有相交；否则没有相交……

感觉就是思想重要，其他的和那时做的强连通题都差不多的，主要是连边问题比较难……慢慢来吧

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 200005
#define MN 1010
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
int n,m,LOW[MN],DFN[MN],Stack[MN],belong[MN];
bool vis[MN];
int cnt,tem,Count,top,a[MN],b[MN];
vector<int>e[MM];
void add(int u,int v)
{e[u].push_back(v);
}
void tarjan(int u)
{DFN[u]=LOW[u]=++tem;vis[u]=true;Stack[++top]=u;int v,i,l=e[u].size();for(i=0;i<l;i++){v=e[u][i];if(!DFN[v]){tarjan(v);LOW[u]=min(LOW[u],LOW[v]);}else if(vis[v]&&DFN[v]<LOW[u]) LOW[u]=DFN[v];}if(DFN[u]==LOW[u]){Count++;do{v=Stack[top--];vis[v]=false;belong[v]=Count;}while(v!=u);}
}
bool twoSAT()
{for(int i=0;i<2*m;i++)if(!DFN[i]) tarjan(i);for(int i=0;i<m;i++)if(belong[2*i]==belong[2*i+1]) return false;return true;
}
int main()
{int i,j;sc(n,m);for(i=0;i<m;i++){sc(a[i],b[i]);if(a[i]>b[i]) swap(a[i],b[i]);}for(i=0;i<m;i++)for(j=i+1;j<m;j++)if(a[i]<a[j]&&b[i]<b[j]&&a[j]<b[i]||a[i]>a[j]&&b[i]>b[j]&&a[i]<b[j]){add(2*i,2*j+1);add(2*j+1,2*i);add(2*j,2*i+1);add(2*i+1,2*j);}if(twoSAT()) puts("panda is telling the truth...");else puts("the evil panda is lying again");return 0;
}

这篇关于POJ 3207 2SAT入门的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---