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

题意

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

题解

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

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

Program:

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<algorithm>

#define ll long long

#define oo 1000000007

#define pi acos(-1.0)

#define MAXN 205

using namespace std;

struct node

{

       int x,y;

}line[MAXN];

vector<int> T[MAXN];

int dfn[MAXN],low[MAXN],DfsIndex,tpnum,tp[MAXN],color[MAXN];

bool instack[MAXN],arc[MAXN][MAXN],d[MAXN];

stack<int> mystack;

bool ok(int a,int b)

{

       if (line[a].y>line[b].x && line[a].y<line[b].y)

          if (!(line[a].x>=line[b].x && line[a].x<=line[b].y)) return false;

       if (line[a].x>line[b].x && line[a].x<line[b].y)

          if (!(line[a].y>=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;i<m;i++)

       {

              y=T[x][i];

              if (!dfn[y])

              {

                  tarjan(y);

                  low[x]=min(low[x],low[y]);

              }else

                  if (instack[y]) low[x]=min(low[x],dfn[y]);

       }

       if (dfn[x]==low[x])

       {

              tpnum++;

              do

              {

                    x=mystack.top();

                    mystack.pop();

                    instack[x]=false;

                    tp[x]=tpnum;

              }while (dfn[x]!=low[x]);

       }

       return;

}

bool judge(int m)

{

       int i;

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

          if (tp[i<<1]==tp[(i<<1)|1]) return false;

       return true;

}

void dfs(int x,int m)

{

       int i;

       color[x]=1;

       for (i=0;i<(m<<1);i++) if (tp[i]==x) color[tp[i^1]]=-1;

       for (i=0;i<tpnum;i++)

          if (arc[x][i] && !color[i]) dfs(i,m);

       return;

}

int main()

{

       int i,j,n,m;

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

       {

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

               {

                     int x,y,t;

                     scanf("%d%d",&x,&y);

                     if (x>y) 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<m;i++)

                  for (j=i+1;j<m;j++)

                    if (!ok(i,j))

                    {

                            T[i<<1].push_back((j<<1)|1);

                            T[j<<1].push_back((i<<1)|1);

                            T[(i<<1)|1].push_back(j<<1);

                            T[(j<<1)|1].push_back(i<<1);

                    }

               memset(instack,false,sizeof(instack));

               memset(dfn,0,sizeof(dfn));

               while (!mystack.empty()) mystack.pop();

               DfsIndex=tpnum=0;

               for (i=0;i<(m<<1);i++)

                  if (!dfn[i]) tarjan(i);

               if (!judge(m))

               {

                       printf("Impossible\n");

                       continue;

               }

               memset(arc,false,sizeof(arc));

               memset(d,0,sizeof(d));

               for (i=0;i<(m<<1);i++)

               {

                      int x,num=T[i].size();

                      for (x=0;x<num;x++)

                      {

                            arc[tp[i]][tp[T[i][x]]]=true;

                            d[tp[T[i][x]]]++;

                      }

               }

               memset(color,0,sizeof(color));

               for (i=0;i<tpnum;i++)

                  if (!color[i]) dfs(i,m);

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

                  if (color[tp[i<<1]]==1) printf("i");

                    else printf("o");

               printf("\n");

       }

       return 0;

}

巴特西

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

最新文章

热门文章