银河

AcWing-368-银河

分析

见《进阶指南》第417页。

实现

#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

typedef long long LL;
const int N = 100010, M = 300010;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N], in_deg[N];
struct node {
    int u, v, w;
};
int n, m;
vector<node> rec;
int cnt, dfn[N], low[N];
stack<int> s;
bool in_stack[N];
int tot, scc[N], Size[N];
int f[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void tarjan (int cur) {
    low[cur] = dfn[cur] = ++ cnt;
    s.push(cur);
    in_stack[cur] = true;
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (dfn[to] == 0) {
            tarjan(to);
            low[cur] = min(low[cur], low[to]);
        } else if (in_stack[to] == true) {
            low[cur] = min(low[cur], dfn[to]);
        }
    }
    if (dfn[cur] == low[cur]) {
        ++ tot;
        int t;
        do {
            t = s.top();
            s.pop();
            in_stack[t] = false;
            scc[t] = tot;
            ++ Size[tot];
        } while (t != cur);
    }
}
void topo_sort () {
    queue<int> q;
    q.push(scc[0]);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            f[to] = max(f[to], f[cur] + w);
            if (-- in_deg[to] == 0) q.push(to);
        }
    }
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, opt, a, b; i <= m; ++ i) {
        scanf("%d%d%d", &opt, &a, &b);
        if (opt == 1) {
            add_edge(b, a, 0);
            add_edge(a, b, 0);
            rec.push_back({ b, a, 0 });
            rec.push_back({ a, b, 0 });
        } else if (opt == 2) {
            add_edge(a, b, 1);
            rec.push_back({ a, b, 1 });
        } else if (opt == 3) {
            add_edge(b, a, 0);
            rec.push_back({ b, a, 0 });
        } else if (opt == 4) {
            add_edge(b, a, 1);
            rec.push_back({ b, a, 1 });
        } else {
            add_edge(a, b, 0);
            rec.push_back({ a, b, 0 });
        }
    }

    for (int i = 1; i <= n; ++ i) {
        add_edge(0, i, 1);
        rec.push_back({ 0, i, 1 });
    }
    tarjan(0);
    idx = 0;
    memset(head, -1, sizeof(head));
    for (int i = 0; i < rec.size(); ++ i) {
        int u = rec[i].u, v = rec[i].v, w = rec[i].w;
        if (scc[u] == scc[v]) {
            if (w == 1) {
                printf("-1");
                return 0;
            }
        } else {
            add_edge(scc[u], scc[v], w);
            ++ in_deg[scc[v]];
        }
    }
    topo_sort();
    LL res = 0;
    for (int i = 1; i <= tot; ++ i)
        res += (LL)f[i] * Size[i];
    printf("%lld", res);
    return 0;
}