POJ 3648 Wedding (2-SAT强连通缩点法+拓扑排序任意解)

题意：新郎和新娘结婚，来了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