欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-23 09:44:59
题意:新郎和新娘结婚,来了n-1对夫妻,这些夫妻包括新郎之间有暧昧关系(包括男女,男男,女女),我们要求新娘对面不能坐着一对夫妻,也不能坐着有任何暧昧关系的人,另外新郎一定要坐新娘对面。输出时输出坐在新娘这一边的人。题解:2-SAT强连通缩点法+拓扑排序任意解由于新郎也有可能搞暧昧,而对于新娘来说若有与之暧昧的人坐哪里都可以,所以限制条件在新郎那里,我们考虑新郎一侧的人选。我们用0表示丈夫,1表示妻子。由于丈夫和妻子只能坐在两侧,我们可以根据暧昧关系进行建边。主要是我们还得建1->0,表示新...

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