【POJ】3207 Ikki's Story IV - Panda's Trick

题意：一个圆上顺时针依次排列着标号为1～n的点，这些点之间共有m条边相连，每两个点只能在圆内或者圆外连边。问是否存在这些边不相交的方案。（n<=1000, m<=500）

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

using namespace std;

#define zero(x) ((x)<<1)

#define one(x) (zero(x)|1)

const int N=1005;

struct E { int next, to; }e[(N*N)<<2];

int ihead[N], cnt, tot, num, FF[N], LL[N], vis[N], s[N], top, p[N], X[N], Y[N], n, m;

void add(int x, int y) { e[++cnt]=(E){ihead[x], y}; ihead[x]=cnt; }

void tarjan(int x) {

	FF[x]=LL[x]=++tot; s[++top]=x; vis[x]=1;

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

		if(!FF[e[i].to]) tarjan(e[i].to), LL[x]=min(LL[x], LL[e[i].to]);

		else if(vis[x]) LL[x]=min(LL[x], FF[e[i].to]);

	}

	if(FF[x]==LL[x]) {

		int y;

		++num;

		do {

			y=s[top--];

			vis[y]=0;

			p[y]=num;

		} while(x!=y);

	}

}

bool work() {

	int mm=m<<1;

	for(int i=0; i<mm; ++i) if(!FF[i]) tarjan(i);

	for(int i=0; i<mm; i+=2) if(p[i]==p[i+1]) return false;

	return true;

}

void clr() {

	int mm=m<<1;

	memset(ihead, 0, sizeof(int)*(mm));

	memset(FF, 0, sizeof(int)*(mm));

	memset(p, 0, sizeof(int)*(mm));

	cnt=tot=top=num=0;

}

int main() {

	while(~scanf("%d%d", &n, &m)) {

		for(int i=0; i<m; ++i) { scanf("%d%d", &X[i], &Y[i]); if(X[i]>Y[i]) swap(X[i], Y[i]); }

		for(int i=0; i<m; ++i) {

			int a=X[i], b=Y[i];

			for(int j=0; j<m; ++j) if(i!=j) {

				int c=X[j], d=Y[j];

				if((a<c && c<b && (a>d || d>b)) || (a<d && d<b && (a>c || c>b)))

					add(zero(i), one(j)), add(one(i), zero(j));

			}

		}

		if(!work()) puts("the evil panda is lying again");

		else puts("panda is telling the truth...");

		clr();

	}

	return 0;

}

容易发现一条边连圆内那么在圆内的其它边与这条边有交的那么我们就连x->y'。如果一条边连在圆外那么圆外的其他边有交的我们就连x'->y。

那么搞搞就行辣= =

（现在写tarjan缩点辣～具体算法看论文伍昱：《由对称性解2-SAT问题》

秒客网

【POJ】3207 Ikki's Story IV - Panda's Trick

相关文章