首页 > 其他 > 详细

2-sat问题,输出方案,几种方法(赵爽的论文染色解法+其完全改进版)浅析 / POJ3683

时间:2014-05-26 03:57:59      阅读:460      评论:0      收藏:0      [点我收藏+]

本文原创于  复习之用,有新体会,故重新编辑。

2014-02-12 09:26:

2-sat之第二斩!昨天看了半天论文(赵爽的和俉昱的),终于看明白了!好激动有木有!终于理解了赵爽的每一句话!并且用了200+行代码实现,A了!具体过程我是敲了帮天的代码啊!!!不容易啊!步骤如下:

把相关问题编号为01 23 45....,(每个编号为一个命题)奇数为取,偶数不取,那么相邻俩个互逆,于是根据具体情况(check)一下,建立图,tarjan判断有无解,然后顺便再缩点,重新建图(逆图),在对新图拓扑,仔细阅读下面赵爽的话:理解每一句:

如果没有产生矛盾,我们就可以把处在同一个强连通分量中的点和边缩成一个点,得到         
新的有向图G。然后,我们把G中的所有弧反向,得到图G ′ ′ ′′。
现在我们观察 。由于已经进行了缩点的操作,因此 G′′ G′′中一定不存在圈,也就是说,
具有拓扑结构。  G′′
我们把G中所有顶点置为“未着色”。按照拓扑顺序重复下面的操作:  ′′           是啊,先对新图(逆的)拓扑,保存起来,然后开始染色,对每个染成“不选”的还要对其子孙也不选 择,(再次dfs。。。无奈),废了半天啊!!!!下面第一段代码便是!!
1、 选择第一个未着色的顶点x。把x染成红色。
2、 把所有与x矛盾的顶点 (如果存在bb yjjB ? ∈ ,且b属于 j
x代表的强连
通分量, j
b ? 属于 代表的强连通分量,那么 y x和 就是互相矛盾的顶点)
及其子孙全部全部染成蓝色。
y
3、 重复操作1和2,直到不存在未着色的点为止。此时,G′′中被染成红色的
点在图G中对应的顶点集合,就对应着该2-SAT的一组解。

后来在大牛交流中,发现无需拓扑啊!白痴啊!尽在眼前还去自己写什么??!!了解到:每个强连通分量都是在它的所有后继强连通分量被求出之后求得的。因此,如果将同一强连通分量收缩为一个结点而构成一个有向无环图,这些强连通分量被求出的顺序是这一新图的逆拓扑序!!!!
不用再次新图拓扑啊!!!何必多此一举!于是来了第二个代码!!

还没完???的确,染色?大牛证明了(现在证明看来也很容易的),无须如此!直接tarjan即可!详见代码三!!又简单了许多啊!从此,2-sat输出方案,哦?不用怕!!!!so easy!

继续刷几题,练练新剑!

今//三种代码:一次比一次简单,第一次完全按论文进行模拟的,比较繁琐,但是思路清晰,包括俩次建图+拓扑+染色+tarjan+dfs,

建图是关键,每次添加的边要互为假言易位式(一对),最后一种方法最妙,以后都用这样的方法,简单又快捷;

该题题意:某一天结婚的人特别多但是主持婚礼的神父只有一个。婚礼时间从s开始到e结束,神父必须在s到s+d或者e-d到e这段时间内在。给定了n个婚礼的s,e,d,求一种方案能使得神父主持所有的婚礼。

思路:建图简单,数据处理一下,按编号保存,之后:遍历点,取矛盾的点添加假言易位边,缩点(同一个SCC中必然可以互推)来判断有无解,输出方案的话,只需新图(不必真的建),每次取逆拓扑小的(scc[i]小的命题即可)(反证即可)。


#include<iostream>  //5340K	360MS
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;
int n;const int MAX=2001;
struct points      //点,01,23,45.。。相连为一对,x^1取对应点(改变奇偶性)
{
    int from,end;
};
points  point[MAX];
int low[MAX];int dfn[MAX];int visited[MAX];bool is_instack[MAX];stack<int>s;
int times=0; int scc[MAX]; int numblock;
int indgree[MAX]; int tuopoxuliu[MAX]; int color[MAX];  //入度,tuopo序列,染色
vector<int>ans(MAX);              //最终答案
vector<vector<int> >edges(MAX);  //原图
vector<vector<int> >newgraph(MAX); //新图
vector<vector<int> >SCC(MAX);       //保存SCC【i】含有的点
void initialize()
{
    numblock=times=0;
    for(int i=0;i<2*n;i++)
     {
         tuopoxuliu[i]=color[i]=visited[i]=low[i]=dfn[i]=is_instack[i]=0;
         edges[i].clear();
         scc[i]=-1;
     }
}
void tarjan(int u)    //有向图dfs,这个不解释
{
    low[u]=dfn[u]=++times;
    is_instack[u]=1;
    s.push(u);
    int len=edges[u].size();
      for(int i=0;i<len;i++)
      {
          int v=edges[u][i];
          if(visited[v]==0)
           {
               visited[v]=1;
               tarjan(v);
               if(low[u]>low[v])low[u]=low[v];
           }
           else if(is_instack[v]&&dfn[v]<low[u])
           {
               low[u]=dfn[v];
           }
      }
     if(dfn[u]==low[u])
     {
          numblock++;
         int cur;
         do
         {
             cur=s.top();
             is_instack[cur]=0;
             s.pop();
             scc[cur]=numblock;
             SCC[numblock].push_back(cur);     //每个SCC对应哪些点保存起来
         }while(cur!=u);
     }
}
bool agst(points a,points b)    //判断矛盾的点
{
    if(a.from<=b.from&&a.end>b.from)     //注意==号的判定!别因为这个跪了!
        return true;
    if(b.from<=a.from&&b.end>a.from)
        return true;
   return false;
}
bool build_graph_has_solution()           //建图
{
     initialize();
    for(int i=0;i<2*n;i++)
      for(int j=i+1;j<2*n;j++)
      {
          if(((i>>1)!=(j>>1))&&agst(point[i],point[j]))     //有时间冲突
             {
                  if(agst(point[i],point[j^1]))    //和另一个也矛盾,那么i不能选(用A->非A表示)
                     edges[i].push_back(i^1);
                  else
                 {
                    edges[i].push_back(j^1);              //那么选你没我
                    edges[j].push_back(i^1);
                 }
             }
      }
     for(int i=0;i<2*n;i++)
       {
           if(visited[i]==0)
             {
                 visited[i]=1;
                 tarjan(i);
             }
       }
     for(int i=0;i<2*n;i+=2)
     {
       if(scc[i]==scc[i+1])   //矛盾的点在一个SCC中,
        {
            printf("NO\n");
            return false;
        }
     }
     return true;
}
void tuopu()              //新图拓扑,记录拓扑序列(1-numblock)保存之
{
    stack<int>sta;
    int count=1;
    for(int i=1;i<=numblock;i++)    //入度点0点
      if(indgree[i]==0)
         sta.push(i);
   while(!sta.empty())
   {
       int cur=sta.top();
        sta.pop();
       tuopoxuliu[count++]=cur;
      int len4=newgraph[cur].size();     //新图,其孩子入度--
       for(int i=0;i<len4;i++)
             {
                 indgree[newgraph[cur][i]]--;
                 if(indgree[newgraph[cur][i]]==0)
                   sta.push(newgraph[cur][i]);
             }
   }
}
void dfs_unchoose(int u)        //u及其子孙都不选
{
    int len5=newgraph[u].size();
    for(int i=0;i<len5;i++)
     {
         int v=newgraph[u][i];
         if(color[v]!=2)
           {
               color[v]=2;
               dfs_unchoose(v);
           }
     }
}
void solve()
{
    for(int i=0;i<2*n;i++)              //建立新图(逆图,有向无环)
    {
     int len=edges[i].size();
      for(int j=0;j<len;j++)
      {
           int v=edges[i][j];
           bool mark=0;
           if(scc[i]!=scc[v])         //是新图的边      //注意下面哪些是SCC[]
           {
               int len2=newgraph[scc[v]].size();       //删去新图重边(要判断入度)
               for(int k=0;k<len2;k++)
               {
                   if(newgraph[scc[v]][k]==scc[i]){mark=1;break;}
               }
               if(mark)continue;
               newgraph[scc[v]].push_back(scc[i]);        //逆图
               indgree[scc[i]]++;
           }
      }
    }
    tuopu();
    for(int i=1;i<=numblock;i++)         //开始染色,
   {
     int cur=tuopoxuliu[i];
      if(color[cur]==0)                 //0未染色
      {
         color[cur]=1;                  //标记选择
         int len3=SCC[cur].size();      //SCC中,
        for(int j=0;j<len3;j++)
        {
         color[scc[SCC[cur][j]^1]]=2;       //这些点矛盾的点所在的SCC标记为2(不选).
          dfs_unchoose(scc[((SCC[cur][j])^1)]);  //其子孙也不选
        }
      }
   }                                       //染色完毕
   for(int i=1;i<=numblock;i++)          //统计ans
   {
       if(color[i]==1)                   //在同一个SCC中全要
       {
           int len6=SCC[i].size();
           for(int j=0;j<len6;j++)
             {
                 ans[SCC[i][j]/2]=SCC[i][j];
             }
       }
   }
   printf("YES\n");
   for(int i=0;i<n;i++)
   {
       int hour=point[ans[i]].from/60;int miu=point[ans[i]].from%60;
           printf("%02d:%02d ",hour,miu);
         hour=point[ans[i]].end/60; miu=point[ans[i]].end%60;
          printf("%02d:%02d\n",hour,miu);
   }
}
void readin()
{
    for(int i=0;i<n;i++)
    {
       int a1,b1,a2,b2,d;char c;
       scanf("%d%c%d",&a1,&c,&b1); scanf("%d%c%d",&a2,&c,&b2); scanf("%d",&d);
       point[i*2].from=a1*60+b1;      point[i*2].end=a1*60+b1+d;
       point[i*2+1].from=a2*60+b2-d;  point[i*2+1].end=a2*60+b2;
    }
}
int main()
{
        scanf("%d",&n);
          readin();
        if( build_graph_has_solution())
           solve();
}

.
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;
int n;const int MAX=2001;
struct points      //点,01,23,45.。。相连为一对,x^1取对应点(改变奇偶性)
{
    int from,end;
};
points  point[MAX];
int low[MAX];int dfn[MAX];int visited[MAX];bool is_instack[MAX];stack<int>s;
int times=0; int scc[MAX]; int numblock;
 int color[MAX];                  //染色
vector<int>ans(MAX);              //最终答案
vector<vector<int> >edges(MAX);  //原图
vector<vector<int> >newgraph(MAX); //新图
vector<vector<int> >SCC(MAX);       //保存SCC【i】含有的点
void initialize()
{
    numblock=times=0;
    for(int i=0;i<2*n;i++)
     {
         color[i]=visited[i]=low[i]=dfn[i]=is_instack[i]=0;
         edges[i].clear();
         scc[i]=-1;
     }
}
void tarjan(int u)           //有向图dfs,这个不解释
{
    low[u]=dfn[u]=++times;
    is_instack[u]=1;
    s.push(u);
    int len=edges[u].size();
      for(int i=0;i<len;i++)
      {
          int v=edges[u][i];
          if(visited[v]==0)
           {
               visited[v]=1;
               tarjan(v);
               if(low[u]>low[v])low[u]=low[v];
           }
           else if(is_instack[v]&&dfn[v]<low[u])
           {
               low[u]=dfn[v];
           }
      }
     if(dfn[u]==low[u])
     {
          numblock++;
         int cur;
         do
         {
             cur=s.top();
             is_instack[cur]=0;
             s.pop();
             scc[cur]=numblock;
             SCC[numblock].push_back(cur);     //每个SCC对应哪些点保存起来
         }while(cur!=u);
     }
}
bool agst(points a,points b)    //判断矛盾的点
{
    if(a.from<=b.from&&a.end>b.from)     //注意==号的判定!别因为这个跪了!
        return true;
    if(b.from<=a.from&&b.end>a.from)
        return true;
   return false;
}
bool build_graph_has_solution()           //建图
{
     initialize();
    for(int i=0;i<2*n;i++)
      for(int j=i+1;j<2*n;j++)
      {
          if(((i>>1)!=(j>>1))&&agst(point[i],point[j]))     //有时间冲突
             {
                  if(agst(point[i],point[j^1]))    //和另一个也矛盾,那么i不能选(用A->非A表示)
                     edges[i].push_back(i^1);
                  else
                 {
                    edges[i].push_back(j^1);              //那么选你没我
                    edges[j].push_back(i^1);
                 }
             }
      }
     for(int i=0;i<2*n;i++)
       {
           if(visited[i]==0)
             {
                 visited[i]=1;
                 tarjan(i);
             }
       }
     for(int i=0;i<2*n;i+=2)
     {
       if(scc[i]==scc[i+1])   //矛盾的点在一个SCC中,
        {
            printf("NO\n");
            return false;
        }
     }
     return true;
}
void dfs_unchoose(int u)        //u及其子孙都不选
{
    int len5=newgraph[u].size();
    for(int i=0;i<len5;i++)
     {
         int v=newgraph[u][i];
         if(color[v]!=2)
           {
               color[v]=2;
               dfs_unchoose(v);
           }
     }
}
void solve()
{
    for(int i=0;i<2*n;i++)              //建立新图(逆图,有向无环)
    {
     int len=edges[i].size();
      for(int j=0;j<len;j++)
      {
           int v=edges[i][j];
           bool mark=0;
           if(scc[i]!=scc[v])         //是新图的边      //注意下面哪些是SCC[]
           {
               int len2=newgraph[scc[v]].size();       //删去新图重边(要判断入度)
               for(int k=0;k<len2;k++)
               {
                   if(newgraph[scc[v]][k]==scc[i]){mark=1;break;}
               }
               if(mark)continue;
               newgraph[scc[v]].push_back(scc[i]);        //逆图
           }
      }
    }
    for(int i=1;i<=numblock;i++)         //开始染色,
   {
     int cur=i;
      if(color[cur]==0)                 //0未染色
      {
         color[cur]=1;                  //标记选择
         int len3=SCC[cur].size();      //SCC中,
        for(int j=0;j<len3;j++)
        {
         color[scc[SCC[cur][j]^1]]=2;       //这些点矛盾的点所在的SCC标记为2(不选).
          dfs_unchoose(scc[((SCC[cur][j])^1)]);  //其子孙也不选
        }
      }
   }                                       //染色完毕
   for(int i=1;i<=numblock;i++)          //统计ans
   {
       cout<<i<<": "<<endl;

           int len6=SCC[i].size();
             for(int j=0;j<len6;j++)
             {
                 cout<<SCC[i][j]<<" ";
                 cout<<endl;
                if(color[i]==1)                   //在同一个SCC中全要
               {
                cout<<"get:";cout<<SCC[i][j]<<endl;
                 ans[SCC[i][j]/2]=SCC[i][j];
               }
             }

   }
   printf("YES\n");
   for(int i=0;i<n;i++)
   {
       int hour=point[ans[i]].from/60;int miu=point[ans[i]].from%60;
            printf("%02d:%02d ",hour,miu);
         hour=point[ans[i]].end/60; miu=point[ans[i]].end%60;
            printf("%02d:%02d\n",hour,miu);
   }
}
void readin()
{
    for(int i=0;i<n;i++)
    {
       int a1,b1,a2,b2,d;char c;
       scanf("%d%c%d",&a1,&c,&b1); scanf("%d%c%d",&a2,&c,&b2); scanf("%d",&d);
       point[i*2].from=a1*60+b1;      point[i*2].end=a1*60+b1+d;
       point[i*2+1].from=a2*60+b2-d;  point[i*2+1].end=a2*60+b2;
    }
}
int main()
{
        scanf("%d",&n);
          readin();
        if( build_graph_has_solution())
           solve();
}

#include<iostream>  //无需自己拓扑!无需染色!无需重新建图!屌!以后不用怕了!直接秒杀!
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;
int n;const int MAX=2001;
struct points      //点,01,23,45.。。相连为一对,x^1取对应点(改变奇偶性)
{
    int from,end;
};
points  point[MAX];
int low[MAX];int dfn[MAX];int visited[MAX];bool is_instack[MAX];stack<int>s;
int times=0; int scc[MAX]; int numblock;
vector<int>ans(MAX);               //最终答案
vector<vector<int> >edges(MAX);   //原图
void initialize()
{
    numblock=times=0;
    for(int i=0;i<2*n;i++)
     {
         visited[i]=low[i]=dfn[i]=is_instack[i]=0;
         edges[i].clear();
         scc[i]=-1;
     }
}
void tarjan(int u)           //有向图dfs,这个不解释
{
    low[u]=dfn[u]=++times;
    is_instack[u]=1;
    s.push(u);
    int len=edges[u].size();
      for(int i=0;i<len;i++)
      {
          int v=edges[u][i];
          if(visited[v]==0)
           {
               visited[v]=1;
               tarjan(v);
               if(low[u]>low[v])low[u]=low[v];
           }
           else if(is_instack[v]&&dfn[v]<low[u])
           {
               low[u]=dfn[v];
           }
      }
     if(dfn[u]==low[u])
     {
          int cur; numblock++;
         do
         {
             cur=s.top();
             is_instack[cur]=0;
             s.pop();
             scc[cur]=numblock;
         }while(cur!=u);
     }
}
bool agst(points a,points b)    //判断矛盾的点
{
    if(a.from<=b.from&&a.end>b.from)     //注意==号的判定!别因为这个跪了!
        return true;
    if(b.from<=a.from&&b.end>a.from)
        return true;
   return false;
}
bool build_graph_has_solution()           //建图
{
     initialize();
    for(int i=0;i<2*n;i++)
      for(int j=i+1;j<2*n;j++)
      {
          if(((i>>1)!=(j>>1))&&agst(point[i],point[j]))     //有时间冲突
             {
                  if(agst(point[i],point[j^1]))    //和另一个也矛盾,那么i不能选(用A->非A表示)
                     edges[i].push_back(i^1);
                  else
                 {
                    edges[i].push_back(j^1);              //那么选你没我
                    edges[j].push_back(i^1);
                 }
             }
      }
     for(int i=0;i<2*n;i++)
       {
           if(visited[i]==0)
             {
                 visited[i]=1;
                 tarjan(i);
             }
       }
     for(int i=0;i<2*n;i+=2)
     {
       if(scc[i]==scc[i+1])        //矛盾的点在一个SCC中,
        {
            printf("NO\n");
            return false;
        }
     }
     return true;
}
void solve()
{
   for(int i=0;i<2*n;i+=2)          //统计ans
   {
       if(scc[i]<scc[i+1])              //关键!!这样选择!!
         ans[i/2]=i;
       else
          ans[i/2]=i+1;
   }
   printf("YES\n");                
   for(int i=0;i<n;i++)              //还原
   {
       int hour=point[ans[i]].from/60;int miu=point[ans[i]].from%60;
            printf("%02d:%02d ",hour,miu);
         hour=point[ans[i]].end/60; miu=point[ans[i]].end%60;
            printf("%02d:%02d\n",hour,miu);
   }
}
void readin()
{
    for(int i=0;i<n;i++)
    {
       int a1,b1,a2,b2,d;char c;
       scanf("%d%c%d",&a1,&c,&b1); scanf("%d%c%d",&a2,&c,&b2); scanf("%d",&d);
       point[i*2].from=a1*60+b1;      point[i*2].end=a1*60+b1+d;
       point[i*2+1].from=a2*60+b2-d;  point[i*2+1].end=a2*60+b2;
    }
}
int main()
{
        scanf("%d",&n);
          readin();
        if( build_graph_has_solution())
           solve();
}



2-sat问题,输出方案,几种方法(赵爽的论文染色解法+其完全改进版)浅析 / POJ3683,布布扣,bubuko.com

2-sat问题,输出方案,几种方法(赵爽的论文染色解法+其完全改进版)浅析 / POJ3683

原文:http://blog.csdn.net/u011498819/article/details/26734569

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!