P7323 [WC2021] 括号路径

发表于 | 阅读数

题意：$n$ 点 $2m$ 边有向图，有 $k$ 个括号类型。输入 $u,v,w$ 表示有一条从 $u$ 到 $v$，括号类型为 $w$ 的左括号和一条通 $v$ 到 $u$，括号类型为 $w$ 的右括号。问有多少个无序点对满足它们中的一条有向路径的括号连成的字符串是一个合法括号匹配串。

考虑$u\rightarrow v$，则$v\rightarrow u$,

又$u\rightarrow t ,t\rightarrow v$，则一定存在 $u\rightarrow v$。

考虑最简单的单个括号$u\rightarrow a\leftarrow v$,则有$u,v$。

为了方便起见，把方向变反就好统计了

$u\rightarrow a\leftarrow v$ 如果合并了这个，那么相当于缩点了。
要把$v$出去的和$u$出去的再合并一边这里得启发式合并找合并的边，反正最多$m$条边。

根据第二个定理和第一个定理，在一个集合内两两互通，相当于无向边了。/
复杂度应该是$O(m\log^2n)$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <bits/stdc++.h>

using namespace std;


void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> fa(n);
    iota(fa.begin(), fa.end(), 0);
    function<int(int)> find = [&](int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); };
    vector<map<int, int>> cnt(n);
    queue<pair<int, int>> q;

    auto merge = [&](int u, int v) {
        int x = find(u);
        int y = find(v);
        if (x == y)
            return;
        if (cnt[x].size() > cnt[y].size())
            swap(x, y);
        fa[x] = y;

        for (auto [i, j] : cnt[x])
        {
            if (cnt[y].count(i))
            {
                q.push({cnt[y][i], j});
            }
            else
                cnt[y][i] = j;
        }
    };
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--, w--;
        if (cnt[v].count(w))
            q.push({cnt[v][w], u});
        else
            cnt[v][w] = u;
    }
    while (!q.empty())
    {
        auto [u, v] = q.front();
        q.pop();
        merge(u, v);
    }
    vector<int> size(n);
    for (int i = 0; i < n; i++)
        size[find(i)]++;
    ll ans = 0;
    for (int i = 0; i < n; i++)
        if (find(i) == i)
            ans += 1ll * size[i] * (size[i] - 1) / 2;
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
}