P10935 - 银河 题解

1
#include <bits/stdc++.h>
2

3
#define N 100010
4
#define M 300010
5
using namespace std;
6

7
typedef long long ll;
8

9
struct Edge {
10
    int to, ne, w;
11
} edges[M << 1];
12
int h[N], hs[N], idx = 0;
13
int scc_cnt = 0, dfs_cnt = 0;
14
int scc_id[N], scc_size[N];
15
int dfn[N], low[N];
16
int dist[N];
17
stack<int> stk;
18
bool in_stk[N];
19

20
void add(int head[], int a, int b, int w) {
21
    idx++;
22
    edges[idx].to = b;
23
    edges[idx].ne = head[a];
24
    edges[idx].w = w;
25
    head[a] = idx;
26
}
27

28
void tarjan(int u) {
29
    dfn[u] = low[u] = ++dfs_cnt;
30
    stk.push(u);
31
    in_stk[u] = true;
32
    for (int i = h[u]; ~i; i = edges[i].ne) {
33
        int j = edges[i].to;
34
        if (!dfn[j]) {
35
            tarjan(j);
36
            low[u] = min(low[u], low[j]);
37
        } else if (in_stk[j]) {
38
            low[u] = min(low[u], dfn[j]);
39
        }
40
    }
41
    if (dfn[u] == low[u]) {
42
        scc_cnt++;
43
        int t;
44
        do {
45
            t = stk.top();
46
            stk.pop();
47
            in_stk[t] = false;
48
            scc_id[t] = scc_cnt;
49
            scc_size[scc_cnt]++;
50
        } while (t != u);
51
    }
52
}
53

54
int main() {
55
    ios::sync_with_stdio(false);
56
    cin.tie(nullptr);
57
    cout.tie(nullptr);
58

59
    memset(h, -1, sizeof h);
60
    memset(hs, -1, sizeof hs);
61

62
    int n, m;
63
    cin >> n >> m;
64
    for (int i = 1; i <= n; i++) add(h, 0, i, 1);
65
    while (m--) {
66
        int t, a, b;
67
        cin >> t >> a >> b;
68
        if (t == 1) {
69
            add(h, a, b, 0);
70
            add(h, b, a, 0);
71
        } else if (t == 2) add(h, a, b, 1);
72
        else if (t == 3) add(h, b, a, 0);
73
        else if (t == 4) add(h, b, a, 1);
74
        else add(h, a, b, 0);
75
    }
76
    tarjan(0);
77
    for (int i = 0; i <= n; i++) {
78
        for (int j = h[i]; ~j; j = edges[j].ne) {
79
            int k = edges[j].to;
80
            int a = scc_id[i], b = scc_id[k];
81
            if (a == b) {
82
                if (edges[j].w > 0) {
83
                    cout << -1 << endl;
84
                    return 0;
85
                }
86
            } else add(hs, a, b, edges[j].w);
87
        }
88
    }
89
    for (int i = scc_cnt; i >= 1; i--) {
90
        for (int j = hs[i]; ~j; j = edges[j].ne) {
91
            int k = edges[j].to;
92
            dist[k] = max(dist[k], dist[i] + edges[j].w);
93
        }
94
    }
95
    ll res = 0;
96
    for (int i = 1; i <= scc_cnt; i++) res += dist[i] * scc_size[i];
97
    cout << res << endl;
98
    return 0;
99
}