当前位置:网站首页>UVA11294-Wedding(2-SAT)
UVA11294-Wedding(2-SAT)
2022-07-05 23:20:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
The question : Yes n The couple attended a wedding banquet .
Everyone sits on the left or right of a long table . All couples can only sit face to face , Including the bride and groom . The bride can only see people sitting on different sides of her . Yes m It's more than a fight for people , The bride doesn't want to see them sitting on the same side .
Ask if there is a distribution plan to meet the bride's requirements .
Ideas :2-SAT problem . If each couple is a variable xi. If xi by true when , The wife and the bride sit on the same side ;xi by false when , The husband and the bride sit on the same side . When xi and xj When you are both husband , It needs to meet ~xi V ~xj, It means that at most one of the two husbands is sitting on a different side from the bride ; When xi and xj When both are wives . It needs to meet xi V xj. It means that at most only one of the two wives is sitting on a different side from the bride . When xi and xj When opposite sex , It needs to meet ~xi V xj perhaps xi V ~xj One of them . It means that at most one of the two is sitting on a different side from the bride .
in summary . Is to satisfy the husband ~xi, Wife xi. Finally, pay attention to initialization mark[1] = 1.
Code :
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
struct TwoSAT{
int n;
vector<int> g[MAXN * 2];
bool mark[MAXN * 2];
int s[MAXN * 2], c;
bool dfs(int x) {
if (mark[x^1]) return false;
if (mark[x]) return true;
mark[x] = true;
s[c++] = x;
for (int i = 0; i < g[x].size(); i++)
if (!dfs(g[x][i])) return false;
return true;
}
void init(int n) {
this->n = n;
for (int i = 0; i < n * 2; i++)
g[i].clear();
memset(mark, 0, sizeof(mark));
mark[1] = 1;
}
void add_clause(int x, int xval, int y, int yval) {
x = x * 2 + xval;
y = y * 2 + yval;
g[x^1].push_back(y);
g[y^1].push_back(x);
}
bool solve() {
for (int i = 0; i < n * 2; i += 2)
if (!mark[i] && !mark[i + 1]) {
c = 0;
if (!dfs(i)) {
while (c > 0) mark[s[--c]] = false;
if (!dfs(i + 1)) return false;
}
}
return true;
}
};
TwoSAT solver;
int n, m;
int main() {
while (scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
solver.init(n);
char a, b;
int xval, yval, u, v;
while (m--) {
scanf("%d%c%d%c", &u, &a, &v, &b);
xval = (a == 'h') ? 0 : 1; yval = (b == 'h') ? 0 : 1; solver.add_clause(u, xval, v, yval); } if (!solver.solve()) printf("bad luck\n"); else { for (int i = 1; i < n; i++) { printf("%d%c", i, solver.mark[2*i] ? 'h' : 'w'); if (i == n - 1) printf("\n"); else printf(" "); } } } return 0;}
Copyright notice : This article is an original blog article , Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117543.html Link to the original text :https://javaforall.cn
边栏推荐
猜你喜欢
东南亚电商指南,卖家如何布局东南亚市场?
From the perspective of quantitative genetics, why do you get the bride price when you get married
Hainan Nuanshen tea recruits warmhearted people: recruitment of the product experience recommender of Nuanshen multi bubble honey orchid single cluster
两数之和、三数之和(排序+双指针)
February 13, 2022-4-symmetric binary tree
Getting started stm32--gpio (running lantern) (nanny level)
[screen recording] how to record in the OBS area
并查集实践
2022 G3 boiler water treatment simulation examination and G3 boiler water treatment simulation examination question bank
Common JVM tools and optimization strategies
随机推荐
数据库基础知识(面试)
Composition of interface
The maximum happiness of the party
Southeast Asia e-commerce guide, how do sellers layout the Southeast Asia market?
Expectation, variance and covariance
How to design API return code (error code)?
Three.JS VR看房
(4)UART应用设计及仿真验证2 —— RX模块设计(无状态机)
Common JVM tools and optimization strategies
芯源&立创EDA训练营——无刷电机驱动
poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)
3D reconstruction of point cloud
二叉树递归套路总结
Common static methods of math class
UVA – 11637 garbage remembering exam (combination + possibility)
PLC编程基础之数据类型、变量声明、全局变量和I/O映射(CODESYS篇 )
Fix the memory structure of JVM in one article
Element operation and element waiting in Web Automation
CJ mccullem autograph: to dear Portland
leecode-学习笔记