POJ 3207 - Ikki's Story IV - Panda's Trick 构图2-sat

POJ 3207 - Ikki's Story IV - Panda's Trick 构图2-sat

题意:

有0~n-1个点按顺序围成一圈..现在在某些两点间加边..这条边要么在圆内..要么在圆外..问能否保证这些线段都不相交      题解:             每个线段有两种状态..里面or外面..又有些线段的某些状态是不能共存的..抽象出2-sat模型..每条线段作为一个组..线段的两种状态作为这个组的两个点..以线段相交的情况来做点之间的有向边..然后用tarjan跑强联通分量..判断每个线段的两种状态是否在一个强联通里..若在..说明一定有线段相交..

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 1005using namespace std; struct node{ int x,y;}line[MAXN];int n,m,DfsIndex,tpnum,tp[MAXN],dfn[MAXN],low[MAXN];bool instack[MAXN];vector T[MAXN];stack mystack;bool ok(int a,int b) //判断两直线是否相交 { int cnt=0; if (line[a].x>=line[b].x && line[a].x<=line[b].y) cnt++; if (line[a].y>=line[b].x && line[a].y<=line[b].y) cnt++; if (cnt==1) return false; return true;} void tarjan(int x){ int i,y,m=T[x].size(); dfn[x]=low[x]=++DfsIndex; instack[x]=true; mystack.push(x); for (i=0;iy) t=x,x=y,y=t; line[i].x=x,line[i].y=y; } for (i=0;i<(m<<1);i++) T[i].clear(); for (i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。