题意：新郎和新娘结婚，来了n-1对夫妻，这些夫妻包括新郎之间有暧昧关系（包括男女，男男，女女），我们要求新娘对面不能坐着一对夫妻，也不能坐着有任何暧昧关系的人，另外新郎一定要坐新娘对面。输出时输出坐在新娘这一边的人。
题解：2-SAT强连通缩点法+拓扑排序任意解
由于新郎也有可能搞暧昧，而对于新娘来说若有与之暧昧的人坐哪里都可以，所以限制条件在新郎那里，我们考虑新郎一侧的人选。
我们用0表示丈夫，1表示妻子。
由于丈夫和妻子只能坐在两侧，我们可以根据暧昧关系进行建边。
主要是我们还得建1->0，表示新娘与新郎不同边。
最后输出要反过来，因为我们选的是新郎这一边的。
我要评论#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
//2-SAT 强连通缩点 (拓扑排序得到任意解)
const int MAXN = 1010;
const int MAXM = 100010;
struct Edge {
int to, next;
}edge[MAXM];
int head[MAXN], tot;
void init() {
tot = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v) {
edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;
}
int Low[MAXN], DFN[MAXN], Stack[MAXN], Belong[MAXN];//Belong 数组的值 1∼scc
int Index, top;
int scc;
bool Instack[MAXN];
int num[MAXN];
void Tarjan(int u) {
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
for (int i = head[u]; ~i; i = edge[i].next) {
v = edge[i].to;
if (!DFN[v]) {
Tarjan(v);
if (Low[u] > Low[v])Low[u] = Low[v];
}
else if (Instack[v] && Low[u] > DFN[v])
Low[u] = DFN[v];
}
if (Low[u] == DFN[u]) {
scc++;
do {
v = Stack[--top];
Instack[v] = false;
Belong[v] = scc;
num[scc]++;
} while (v != u);
}
}
bool solvable(int n) {
memset(DFN, 0, sizeof(DFN));
memset(Instack, false, sizeof(Instack));
memset(num, 0, sizeof(num));
Index = scc = top = 0;
for (int i = 0; i < n; i++)
if (!DFN[i])
Tarjan(i);
for (int i = 0; i < n; i += 2) {
if (Belong[i] == Belong[i ^ 1])
return false;
}
return true;
}
//拓扑排序求任意一组解部分
queue<int>q1, q2;
vector<vector<int> > dag;//缩点后的逆向 DAG 图
char color[MAXN];//染色，为 1 是选择的
int indeg[MAXN];//入度
int cf[MAXN];
void solve(int n) {
dag.assign(scc + 1, vector<int>());
memset(indeg, 0, sizeof(indeg));
memset(color, 0, sizeof(color));
for (int u = 0; u < n; u++)
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (Belong[u] != Belong[v]) {
dag[Belong[v]].push_back(Belong[u]);
indeg[Belong[u]]++;
}
}
for (int i = 0; i < n; i += 2) {
cf[Belong[i]] = Belong[i ^ 1];
cf[Belong[i ^ 1]] = Belong[i];
}
while (!q1.empty()) q1.pop();
while (!q2.empty()) q2.pop();
for (int i = 1; i <= scc; i++)
if (indeg[i] == 0)
q1.push(i);
while (!q1.empty()) {
int u = q1.front();
q1.pop();
if (color[u] == 0) {
color[u] = 1;
color[cf[u]] = -1;
}
int sz = dag[u].size();
for (int i = 0; i < sz; i++) {
indeg[dag[u][i]]--;
if (indeg[dag[u][i]] == 0)
q1.push(dag[u][i]);
}
}
}
int n, m, u, v;
char a, b;
int main() {
while (scanf("%d%d", &n, &m) && n) {
init();
for (int i = 1; i <= m; i++) {
scanf("%d%c %d%c", &u, &a, &v, &b);
u = u * 2 + (a == 'h' ? 0 : 1); //0丈夫 1妻子
v = v * 2 + (b == 'h' ? 0 : 1);
addedge(u, v ^ 1);
addedge(v, u ^ 1);
}
addedge(1, 0); //表示选了妻子就会选丈夫，这样就会矛盾，所以结果里不会包含妻子
if (solvable(2 * n)) {
solve(2 * n);
for (int i = 1; i <= n - 1; i++) {
if (color[Belong[2 * i]] == 1) printf("%dw ", i); //我们选的丈夫一侧的，所以输出反过来
else printf("%dh ", i);
}
puts("");
}
else puts("bad luck");
}
return 0;
}
本文地址：https://blog.csdn.net/qq_43680965/article/details/107341387
如对本文有疑问， 点击进行留言回复！！
从零开始的PYTHON3摸鱼（二）windows如何运行python，编辑器选择
网友评论