首页 > 代码库 > 2-sat
2-sat
Let‘s go home http://acm.hdu.edu.cn/showproblem.php?pid=1824
把队长和两个队员当成对称的两个点，有你没我，有我没你。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<stack> 5 #include<map> 6 #define mt(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 class TwoSat { ///2-sat判定,solve函数返回是否有解,i结点的对称结点i^为i+n, 9 static const int ME=10010;///边的个数 10 static const int MV=2010;///点的个数 11 struct G { 12 struct E { 13 int u,v,next; 14 } e[ME]; 15 int le,head[MV]; 16 void init() { 17 le=0; 18 mt(head,-1); 19 } 20 void add(int u,int v) { 21 e[le].u=u; 22 e[le].v=v; 23 e[le].next=head[u]; 24 head[u]=le++; 25 } 26 } g; 27 class Tarjan { ///有向图强连通分量缩点o(MV+ME) 28 int Index,Bcnt,num[MV],belong[MV],dfn[MV],low[MV]; 29 bool instack[MV]; 30 stack<int> s; 31 void tarjan(int u) { 32 dfn[u]=low[u]=++Index; 33 instack[u]=true; 34 s.push(u); 35 int v; 36 for(int i=g.head[u]; ~i; i=g.e[i].next) { 37 v=g.e[i].v; 38 if(!dfn[v]) { 39 tarjan(v); 40 low[u]=min(low[u],low[v]); 41 } else if(instack[v]) { 42 low[u]=min(low[u],dfn[v]); 43 } 44 } 45 if(dfn[u]==low[u]) { 46 Bcnt++; 47 do { 48 v=s.top(); 49 s.pop(); 50 instack[v]=false; 51 belong[v]=Bcnt; 52 num[Bcnt]++; 53 } while(u!=v); 54 } 55 } 56 public: 57 G g; 58 void init() { 59 g.init(); 60 Index=Bcnt=0; 61 mt(num,0); 62 mt(dfn,0); 63 mt(low,0); 64 mt(instack,0); 65 while(!s.empty()) s.pop(); 66 } 67 void add(int u,int v) { 68 g.add(u,v); 69 } 70 void solve(int n) {///传入点数，点下标1开始 71 for(int i=1; i<=n; i++) { 72 if(!dfn[i]) { 73 tarjan(i); 74 } 75 } 76 } 77 int getbcnt() {///强连通分量的个数 78 return Bcnt; 79 } 80 int getbelong(int id) {///属于哪个分量，分量下标1开始 81 return belong[id]; 82 } 83 int getnum(int id) {///某个分量的点的个数 84 return num[id]; 85 } 86 } T; 87 class Unitenode { ///缩点 88 G ug; 89 int n,in[MV]; 90 bool mat[MV][MV]; 91 queue<int> q; 92 public: 93 void init(int tn) { 94 n=tn; 95 ug.init(); 96 mt(in,0); 97 for(int i=1;i<=n;i++) 98 for(int j=1;j<=n;j++) 99 mat[i][j]=i==j?true:false;100 }101 void add(int u,int v) {102 if(!mat[u][v]) {103 in[v]++;104 mat[u][v]=true;105 ug.add(u,v);106 }107 }108 void solve(int tp[]) {109 while(!q.empty()) q.pop();110 for(int i=1; i<=n; i++) {111 if(!in[i]) {112 q.push(i);113 }114 }115 int ret=1;116 while(!q.empty()) {117 int u=q.front();118 q.pop();119 tp[ret++]=u;120 for(int i=ug.head[u]; ~i; i=ug.e[i].next) {121 int v=ug.e[i].v;122 in[v]--;123 if(!in[v]) {124 q.push(v);125 }126 }127 }128 }129 } U;130 void unite() {131 U.init(T.getbcnt());132 for(int i=1; i<=n; i++) {133 for(int j=T.g.head[i]; ~j; j=T.g.e[j].next) {134 U.add(T.getbelong(i),T.getbelong(T.g.e[j].v));135 }136 }137 }138 int n,tp[MV];139 bool flag[MV];140 public:141 void init(int tn) { ///传入判定结点2*n142 n=tn;143 T.init();144 }145 void add(int u,int v) { ///如果取u必须取v结点添加边u->v,下标1开始146 T.add(u,v);147 }148 bool solve() {149 T.solve(n);150 for(int i=1,z=n/2; i<=z; i++) {151 if(T.getbelong(i)==T.getbelong(i+z))return false;152 }153 return true;154 }155 void output(bool ans[]) {///ans[i]==false则选择i结点，否则选择i^结点156 unite();157 U.solve(tp);158 mt(flag,0);159 for(int i=T.getbcnt(); i>0; i--) {160 for(int j=1,y; j<=n; j++) {161 if(j>n/2)y=j-n/2;162 else y=j;163 if(!flag[y]&&T.getbelong(j)==tp[i]) {164 flag[y]=true;165 if(j>n/2) {166 ans[j-n/2]=true;167 } else {168 ans[j]=false;169 }170 }171 }172 }173 }174 } gx;175 int mp[3010];176 int main() {177 int n,m,x,y,z;178 while(~scanf("%d%d",&n,&m)) {179 gx.init(n*2);180 int myid=1;181 for(int i=0; i<n; i++) {182 scanf("%d%d%d",&x,&y,&z);183 mp[x]=myid;184 mp[y]=myid+n;185 mp[z]=myid+n;186 myid++;187 }188 for(int i=0; i<m; i++) {189 scanf("%d%d",&x,&y);190 x=mp[x];191 y=mp[y];192 gx.add(x,y+(y>n?-n:n));193 gx.add(y,x+(x>n?-n:n));194 }195 if(gx.solve()) {196 puts("yes");197 } else {198 puts("no");199 }200 }201 return 0;202 }
Party http://acm.hdu.edu.cn/showproblem.php?pid=3062
根据矛盾关系建图
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<stack> 5 #include<map> 6 #define mt(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 class TwoSat { ///2-sat判定,solve函数返回是否有解,i结点的对称结点i^为i+n, 9 static const int ME=1000010;///边的个数 10 static const int MV=2010;///点的个数 11 struct G { 12 struct E { 13 int u,v,next; 14 } e[ME]; 15 int le,head[MV]; 16 void init() { 17 le=0; 18 mt(head,-1); 19 } 20 void add(int u,int v) { 21 e[le].u=u; 22 e[le].v=v; 23 e[le].next=head[u]; 24 head[u]=le++; 25 } 26 } g; 27 class Tarjan { ///有向图强连通分量缩点o(MV+ME) 28 int Index,Bcnt,num[MV],belong[MV],dfn[MV],low[MV]; 29 bool instack[MV]; 30 stack<int> s; 31 void tarjan(int u) { 32 dfn[u]=low[u]=++Index; 33 instack[u]=true; 34 s.push(u); 35 int v; 36 for(int i=g.head[u]; ~i; i=g.e[i].next) { 37 v=g.e[i].v; 38 if(!dfn[v]) { 39 tarjan(v); 40 low[u]=min(low[u],low[v]); 41 } else if(instack[v]) { 42 low[u]=min(low[u],dfn[v]); 43 } 44 } 45 if(dfn[u]==low[u]) { 46 Bcnt++; 47 do { 48 v=s.top(); 49 s.pop(); 50 instack[v]=false; 51 belong[v]=Bcnt; 52 num[Bcnt]++; 53 } while(u!=v); 54 } 55 } 56 public: 57 G g; 58 void init() { 59 g.init(); 60 Index=Bcnt=0; 61 mt(num,0); 62 mt(dfn,0); 63 mt(low,0); 64 mt(instack,0); 65 while(!s.empty()) s.pop(); 66 } 67 void add(int u,int v) { 68 g.add(u,v); 69 } 70 void solve(int n) {///传入点数，点下标1开始 71 for(int i=1; i<=n; i++) { 72 if(!dfn[i]) { 73 tarjan(i); 74 } 75 } 76 } 77 int getbcnt() {///强连通分量的个数 78 return Bcnt; 79 } 80 int getbelong(int id) {///属于哪个分量，分量下标1开始 81 return belong[id]; 82 } 83 int getnum(int id) {///某个分量的点的个数 84 return num[id]; 85 } 86 } T; 87 class Unitenode { ///缩点 88 G ug; 89 int n,in[MV]; 90 bool mat[MV][MV]; 91 queue<int> q; 92 public: 93 void init(int tn) { 94 n=tn; 95 ug.init(); 96 mt(in,0); 97 for(int i=1;i<=n;i++) 98 for(int j=1;j<=n;j++) 99 mat[i][j]=i==j?true:false;100 }101 void add(int u,int v) {102 if(!mat[u][v]) {103 in[v]++;104 mat[u][v]=true;105 ug.add(u,v);106 }107 }108 void solve(int tp[]) {109 while(!q.empty()) q.pop();110 for(int i=1; i<=n; i++) {111 if(!in[i]) {112 q.push(i);113 }114 }115 int ret=1;116 while(!q.empty()) {117 int u=q.front();118 q.pop();119 tp[ret++]=u;120 for(int i=ug.head[u]; ~i; i=ug.e[i].next) {121 int v=ug.e[i].v;122 in[v]--;123 if(!in[v]) {124 q.push(v);125 }126 }127 }128 }129 } U;130 void unite() {131 U.init(T.getbcnt());132 for(int i=1; i<=n; i++) {133 for(int j=T.g.head[i]; ~j; j=T.g.e[j].next) {134 U.add(T.getbelong(i),T.getbelong(T.g.e[j].v));135 }136 }137 }138 int n,tp[MV];139 bool flag[MV];140 public:141 void init(int tn) { ///传入判定结点2*n142 n=tn;143 T.init();144 }145 void add(int u,int v) { ///如果取u必须取v结点添加边u->v,下标1开始146 T.add(u,v);147 }148 bool solve() {149 T.solve(n);150 for(int i=1,z=n/2; i<=z; i++) {151 if(T.getbelong(i)==T.getbelong(i+z))return false;152 }153 return true;154 }155 void output(bool ans[]) {///ans[i]==false则选择i结点，否则选择i^结点156 unite();157 U.solve(tp);158 mt(flag,0);159 for(int i=T.getbcnt(); i>0; i--) {160 for(int j=1,y; j<=n; j++) {161 if(j>n/2)y=j-n/2;162 else y=j;163 if(!flag[y]&&T.getbelong(j)==tp[i]) {164 flag[y]=true;165 if(j>n/2) {166 ans[j-n/2]=true;167 } else {168 ans[j]=false;169 }170 }171 }172 }173 }174 } gx;175 int main() {176 int n,m,a,b,c,d;177 while(~scanf("%d%d",&n,&m)) {178 gx.init(n*2);179 for(int i=0; i<m; i++) {180 scanf("%d%d%d%d",&a,&b,&c,&d);181 a++;182 b++;183 if(c==0&&d==0) {184 gx.add(a,b+n);185 gx.add(b,a+n);186 } else if(c==1&&d==1) {187 gx.add(a+n,b);188 gx.add(b+n,a);189 } else if(c==0&&d==1) {190 gx.add(a,b);191 gx.add(b+n,a+n);192 } else if(c==1&&d==0) {193 gx.add(a+n,b+n);194 gx.add(b,a);195 }196 }197 if(gx.solve()) {198 puts("YES");199 } else {200 puts("NO");201 }202 }203 return 0;204 }
D. Ring Road 2 http://codeforces.com/problemset/problem/27/D
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<stack> 5 #include<map> 6 #define mt(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 class TwoSat { ///2-sat判定,solve函数返回是否有解,i结点的对称结点i^为i+n, 9 static const int ME=1000010;///边的个数 10 static const int MV=2010;///点的个数 11 struct G { 12 struct E { 13 int u,v,next; 14 } e[ME]; 15 int le,head[MV]; 16 void init() { 17 le=0; 18 mt(head,-1); 19 } 20 void add(int u,int v) { 21 e[le].u=u; 22 e[le].v=v; 23 e[le].next=head[u]; 24 head[u]=le++; 25 } 26 } g; 27 class Tarjan { ///有向图强连通分量缩点o(MV+ME) 28 int Index,Bcnt,num[MV],belong[MV],dfn[MV],low[MV]; 29 bool instack[MV]; 30 stack<int> s; 31 void tarjan(int u) { 32 dfn[u]=low[u]=++Index; 33 instack[u]=true; 34 s.push(u); 35 int v; 36 for(int i=g.head[u]; ~i; i=g.e[i].next) { 37 v=g.e[i].v; 38 if(!dfn[v]) { 39 tarjan(v); 40 low[u]=min(low[u],low[v]); 41 } else if(instack[v]) { 42 low[u]=min(low[u],dfn[v]); 43 } 44 } 45 if(dfn[u]==low[u]) { 46 Bcnt++; 47 do { 48 v=s.top(); 49 s.pop(); 50 instack[v]=false; 51 belong[v]=Bcnt; 52 num[Bcnt]++; 53 } while(u!=v); 54 } 55 } 56 public: 57 G g; 58 void init() { 59 g.init(); 60 Index=Bcnt=0; 61 mt(num,0); 62 mt(dfn,0); 63 mt(low,0); 64 mt(instack,0); 65 while(!s.empty()) s.pop(); 66 } 67 void add(int u,int v) { 68 g.add(u,v); 69 } 70 void solve(int n) {///传入点数，点下标1开始 71 for(int i=1; i<=n; i++) { 72 if(!dfn[i]) { 73 tarjan(i); 74 } 75 } 76 } 77 int getbcnt() {///强连通分量的个数 78 return Bcnt; 79 } 80 int getbelong(int id) {///属于哪个分量，分量下标1开始 81 return belong[id]; 82 } 83 int getnum(int id) {///某个分量的点的个数 84 return num[id]; 85 } 86 } T; 87 class Unitenode { ///缩点 88 G ug; 89 int n,in[MV]; 90 bool mat[MV][MV]; 91 queue<int> q; 92 public: 93 void init(int tn) { 94 n=tn; 95 ug.init(); 96 mt(in,0); 97 for(int i=1;i<=n;i++) 98 for(int j=1;j<=n;j++) 99 mat[i][j]=i==j?true:false;100 }101 void add(int u,int v) {102 if(!mat[u][v]) {103 in[v]++;104 mat[u][v]=true;105 ug.add(u,v);106 }107 }108 void solve(int tp[]) {109 while(!q.empty()) q.pop();110 for(int i=1; i<=n; i++) {111 if(!in[i]) {112 q.push(i);113 }114 }115 int ret=1;116 while(!q.empty()) {117 int u=q.front();118 q.pop();119 tp[ret++]=u;120 for(int i=ug.head[u]; ~i; i=ug.e[i].next) {121 int v=ug.e[i].v;122 in[v]--;123 if(!in[v]) {124 q.push(v);125 }126 }127 }128 }129 } U;130 void unite() {131 U.init(T.getbcnt());132 for(int i=1; i<=n; i++) {133 for(int j=T.g.head[i]; ~j; j=T.g.e[j].next) {134 U.add(T.getbelong(i),T.getbelong(T.g.e[j].v));135 }136 }137 }138 int n,tp[MV];139 bool flag[MV];140 public:141 void init(int tn) { ///传入判定结点2*n142 n=tn;143 T.init();144 }145 void add(int u,int v) { ///如果取u必须取v结点添加边u->v,下标1开始146 T.add(u,v);147 }148 bool solve() {149 T.solve(n);150 for(int i=1,z=n/2; i<=z; i++) {151 if(T.getbelong(i)==T.getbelong(i+z))return false;152 }153 return true;154 }155 void output(bool ans[]) {///ans[i]==false则选择i结点，否则选择i^结点156 unite();157 U.solve(tp);158 mt(flag,0);159 for(int i=T.getbcnt(); i>0; i--) {160 for(int j=1,y; j<=n; j++) {161 if(j>n/2)y=j-n/2;162 else y=j;163 if(!flag[y]&&T.getbelong(j)==tp[i]) {164 flag[y]=true;165 if(j>n/2) {166 ans[j-n/2]=true;167 } else {168 ans[j]=false;169 }170 }171 }172 }173 }174 } gx;175 const int M=128;176 struct IN {177 int x,y;178 } in[M];179 bool ok(int i,int j) {180 if(in[i].x<in[j].x&&in[j].x<in[i].y&&in[i].y<in[j].y) return true;181 return false;182 }183 bool judge(int i,int j) {184 if(ok(i,j)||ok(j,i)) return true;185 return false;186 }187 bool ans[M];188 int main() {189 int n,m;190 while(~scanf("%d%d",&n,&m)) {191 gx.init(m*2);192 for(int i=1; i<=m; i++) {193 scanf("%d%d",&in[i].x,&in[i].y);194 if(in[i].x>in[i].y) swap(in[i].x,in[i].y);195 }196 for(int i=1; i<=m; i++) {197 for(int j=i+1; j<=m; j++) {198 if(judge(i,j)) {199 // printf("%d %d\n",i,j);200 gx.add(i,j+m);201 gx.add(j,i+m);202 gx.add(i+m,j);203 gx.add(j+m,i);204 }205 }206 }207 if(gx.solve()) {208 gx.output(ans);209 for(int i=1; i<=m; i++) {210 if(ans[i]) printf("i");211 else printf("o");212 }213 puts("");214 } else {215 puts("Impossible");216 }217 }218 return 0;219 }
end
2-sat
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。