当前位置:网站首页>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
边栏推荐
- Element operation and element waiting in Web Automation
- 并查集实践
- 透彻理解JVM类加载子系统
- Alibaba Tianchi SQL training camp task4 learning notes
- 【经典控制理论】自控实验总结
- 3D reconstruction of point cloud
- Hcip day 11 (BGP agreement)
- 媒体查询:引入资源
- UVA – 11637 garbage remembering exam (combination + possibility)
- The PNG image is normal when LabVIEW is opened, and the full black image is obtained when Photoshop is opened
猜你喜欢
利用LNMP实现wordpress站点搭建
Non rigid / flexible point cloud ICP registration
YML configuration, binding and injection, verification, unit of bean
Go language implementation principle -- lock implementation principle
Alibaba Tianchi SQL training camp task4 learning notes
Three.JS VR看房
[untitled]
Common JVM tools and optimization strategies
How to design API return code (error code)?
Selenium+pytest automated test framework practice
随机推荐
From the perspective of quantitative genetics, why do you get the bride price when you get married
Development specification: interface unified return value format [resend]
实现反向代理客户端IP透传
【经典控制理论】自控实验总结
openresty ngx_ Lua request response
3D point cloud slam
Mathematical formula screenshot recognition artifact mathpix unlimited use tutorial
How to quickly understand complex businesses and systematically think about problems?
White hat talks about web security after reading 2
LeetCode145. Post order traversal of binary tree (three methods of recursion and iteration)
February 13, 2022-4-symmetric binary tree
openresty ngx_lua请求响应
Scala concurrent programming (II) akka
Hcip day 11 (BGP agreement)
One article deals with the microstructure and instructions of class
Southeast Asia e-commerce guide, how do sellers layout the Southeast Asia market?
秒杀系统的设计与实现思路
使用rewrite规则实现将所有到a域名的访问rewrite到b域名
Creative mode 1 - single case mode
2.13 summary