POJ-3683-Priest John's Busiest Day(2-sat)-白红宇

POJ-3683-Priest John's Busiest Day(2-sat)

阅读量：5327 次

发布时间：2019-06-14

本文共 1328 字，大约阅读时间需要 4 分钟。

POJ 2-sat六题之三

http://blog.sina.com.cn/s/blog_64675f540100k1cd.html

题目描述：有n个婚礼，每个婚礼有起始时间si，结束时间ti，还有一个主持时间ti，ti必须安排在婚礼的开始或者结束，主持由祭祀来做，但是只有一个祭祀，所以各个婚礼的主持时间不能重复，问你有没有可能正常的安排主持时间，不能输出no，能的话要输出具体的答案：即每个婚礼的主持时间段是什么样的。

解题报告：

对于每个婚礼，主持时间只有两种状态，而且各个婚礼之间的主持时间之间有相互限制，所以想到2-sat。

构图：

对于婚礼i和婚礼j。i表示在开始主持，i2表示在结束主持，j类似。

枚举每一对不同的i和j。

如果i和j冲突。连接i j2

如果i和j2冲突，连接i j

如果i2和j冲突，连接i2 j2

如果i2和j2冲突，连接i2 j

// File Name: 3683.cpp// Author: zlbing// Created Time: 2013/1/30 13:43:55#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               using namespace std;#define MAXN 1050int T[MAXN][3];struct TwoSAT{ int n; vector
               
                G[MAXN*2]; bool mark[MAXN*2]; stack
                
                 S; bool dfs(int x) { if(mark[x^1])return false; if(mark[x])return true; mark[x]=true; S.push(x); for(int i=0;i
                 
                  T[i][0]&&T[i][0]+T[i][2]>T[j][0]) solver.add_clause(i*2,2*j+1); if(T[j][1]>T[i][0]&&T[i][0]+T[i][2]>T[j][1]-T[j][2]) solver.add_clause(i*2,2*j); if(T[j][0]+T[j][2]>T[i][1]-T[i][2]&&T[i][1]>T[j][0]) solver.add_clause(i*2+1,2*j+1); if(T[j][1]>T[i][1]-T[i][2]&&T[i][1]>T[j][1]-T[j][2]) solver.add_clause(i*2+1,2*j); } if(!solver.solve()) printf("NO\n"); } return 0;}

转载于:https://www.cnblogs.com/arbitrary/archive/2013/01/30/2883829.html

你可能感兴趣的文章