CodeForces 27D - Ring Road 2 构图2-sat..并输出选择方案

CodeForces 27D - Ring Road 2 构图2-sat..并输出选择方案

题意

n个数1~n按顺序围成一个圈...现在在某些两点间加边..边可以加在圈内或者圈外..问是否会发生冲突？如果不发生冲突..输每一条边是放圈内还是圈外.

题解

这道题和POJ 3207差不多了..只是那道题只要判断是否存在不要输出方案...发现个很严重的问题..POJ 3207的数据实在是太弱了..我上一个程序里判断两个线段是否相交是个错了..都让我AC了..导致我做这题是沿用了思路...浪费了很多时间...

先把每条线段看成一个组连个点..圈外和圈内..然后根据线段的冲突关系构造2-sat图..用tarjan做强联通分量判断是否存在方案使得每个线段都不冲突..并且将每个强联通分量缩成一个点,..若存在方案..开始找方案..将缩点后的图构造好..得到的会是一个有向无环图(要是有环那两个强联通分量就应该合并了..所以无环)..按照拓扑排序从入度为0的点进入...对到达的点染色(也就是标记)..并且将对应的一些点也染色(就是同一组的另一个,标记为另一个颜色)...最后根据染色输出每条边的内外..

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 205using namespace std; struct node{ int x,y;}line[MAXN];vector T[MAXN];int dfn[MAXN],low[MAXN],DfsIndex,tpnum,tp[MAXN],color[MAXN];bool instack[MAXN],arc[MAXN][MAXN],d[MAXN];stack mystack;bool ok(int a,int b){ if (line[a].y>line[b].x && line[a].y=line[b].x && line[a].x<=line[b].y)) return false; if (line[a].x>line[b].x && line[a].x=line[b].x && line[a].y<=line[b].y)) 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小时内删除侵权内容。