首页 > 其他 > 详细

LA3713 2-sat(用到两种矛盾关系)

时间:2014-03-07 10:49:29      阅读:409      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
  1 /*LA3713
  2 典型的2-sat模型
  3 宇航员分两类:
  4 1、年龄少于平均 young
  5 2、至少为平均
  6 矛盾:
  7 情况一:如果两个宇航员属于同一类且相互矛盾的话,则他们两个的选择一定是不相同的
  8 情况二:如果不属于同一组相互矛盾,不能同时选C任务
  9 建模:A/B 2*i
 10       C  2*i+1
 11 情况一:2x-->2y+1,2x+1-->2y;2y-->2x+1;2y+1-->2x;
 12 情况二:2x+1-->2y,2y+1-->2x;
 13 
 14 */
 15 #include <stdio.h>
 16 #include <stdlib.h>
 17 #include <string.h>
 18 #include <math.h>
 19 #include <ctype.h>
 20 #include <string>
 21 #include <iostream>
 22 #include <sstream>
 23 #include <vector>
 24 #include <queue>
 25 #include <stack>
 26 #include <map>
 27 #include <list>
 28 #include <set>
 29 #include <algorithm>
 30 #define INF 0x3f3f3f3f
 31 #define LL long long
 32 #define eps 1e-4
 33 #define maxn 100010
 34 using namespace std;
 35 int Age[maxn];
 36 int n,m;
 37 double Aver;
 38 int nextint(){int x;scanf("%d",&x);return x;}
 39 int kind(int age)
 40 {
 41     if (Aver-age>eps) return 2;else return 1;//B:young
 42 }
 43 struct TwoSAT
 44 {
 45     int n;
 46     vector<int> G[maxn*2];
 47     bool mark[maxn*2];//联系《2-sat算法解析》中的红蓝标色
 48     int S[maxn*2],c;
 49     bool dfs(int x)
 50     {
 51         if (mark[x^1]) return false;//真假同时被标记,逻辑矛盾
 52         if (mark[x]) return true;//x被标记,意味着下面的节点也被标记,思想是记忆化搜索
 53         mark[x]=true;
 54         S[c++]=x;
 55         for(int i=0; i<G[x].size(); i++)
 56         if(!dfs(G[x][i])) return false; //同一个强联通分量应该表上同一种颜色
 57         return true;
 58     }
 59     void init(int n)
 60     {
 61         this->n=n;
 62         for(int i=0; i<n*2; i++) G[i].clear();
 63         memset(mark,0,sizeof(mark));
 64     }
 65     //x=xval or y=xval ,x 则 xval=0,x‘则xval=1
 66     void add_clause(int x ,int y,int k)
 67     {
 68         if(k==0){
 69         G[2*x+1].push_back(2*y);
 70         G[2*y+1].push_back(2*x);
 71         }
 72         if (k==1){
 73         G[2*x].push_back(2*y+1);
 74         G[2*y].push_back(2*x+1);
 75         }
 76     }
 77     bool solve()
 78     {
 79         for(int i=0;i<n*2;i+=2)
 80         {
 81             if(!mark[i] && !mark[i^1])//真假都没被标记才需dfs,思考一下,原书上写的是[mark+1],这是由i的取值和步长决定的,这里更改,使逻辑含义统一
 82             {
 83                 c=0;//记得清零
 84                 if(!dfs(i))//将i标记为true
 85                 {
 86                     while(c>0) mark[S[--c]]=false;
 87                     if (!dfs(i^1)) return false;//更改初始标号颜色。只要有一个对象不能“二选一”,则2-sat无解
 88                 }
 89             }
 90         }
 91         return true;
 92     }
 93     void printans()
 94     {
 95         for(int i=0;i<n;i++)
 96         if (mark[2*i]) printf("%c\n",A+kind(Age[i])-1);else printf("C\n");
 97     }
 98 } sat;
 99 void read()
100 {
101     Aver=0;
102     for(int i=0;i<n;i++) {Age[i]=nextint();Aver+=Age[i];}
103 //    cout<<"a="<<Aver<<endl;
104     Aver=Aver/n;
105 //    cout<<"a="<<Aver<<endl;
106 }
107 void solve()
108 {
109     sat.init(n);
110     for(int i=0;i<m;i++)
111     {
112         int x,y;
113         x=nextint();y=nextint();
114         x--;y--;
115         if(kind(Age[x])==kind(Age[y]))
116         {//2x-->2y+1,2x+1-->2y;2y-->2x+1;2y+1-->2x;//后面的0/1表示连边的方式
117             sat.add_clause(x,y,1);
118             sat.add_clause(x,y,0);
119         }else
120         {//2x+1-->2y,2y+1-->2x;
121             sat.add_clause(x,y,0);
122         }
123     }
124     if(sat.solve()) sat.printans();else printf("No solution.\n");
125 }
126 int main()
127 {
128     while(cin>>n>>m)
129     {
130         if (n==0 && m==0) break;
131         read();
132         solve();
133     }
134     return 0;
135 }
bubuko.com,布布扣

LA3713 2-sat(用到两种矛盾关系),布布扣,bubuko.com

LA3713 2-sat(用到两种矛盾关系)

原文:http://www.cnblogs.com/little-w/p/3585637.html

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