ABC352

E - Clique Connect

https://atcoder.jp/contests/abc352/tasks/abc352\_e

最小生成树

先复习一下最小生成树，这里用Kruscal

  • 生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 (n - 1) 条，将所有顶点连通。
  • 最小生成（Minimum Spanning Tree，MST）：边权和最小的生成树。

运用任意一棵最小生成树一定包含无向图中权值最小的边这个结论，对所有边按权值从小到大排序，贪心加入所有能加入的边即可。

https://www.luogu.com.cn/problem/P3366

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m;
    std::vector<std::tuple<int, int, int>> edges(m);//跟正常存边方式不一样，因为要对边排序
    for (int i = 0, u, v, w; i < m; i++) {std::cin >> u >> v >> w; --u; --v; edges[i] = {w, u, v};}
    ranges::sort(edges);
    DSU dsu(n);
    i64 ans = 0;//维护最小边权和
    int cnt = 0;//维护生成树的边数
    for (const auto&[w, u, v] : edges) if (not dsu.same(u, v)) {//如果该点的两边不连通，就让其联通, 否则说明会成环，只能跳过
        dsu.merge(u, v); ans += w; cnt += 1;
    }

    if (cnt < n - 1) {
        std::cout << "orz\n";//说明无解
    } else {
        std::cout << ans << '\n';
    }

    return 0;
}

那么针对这道题，他是给出了很多组边集，按边权分类。

如果直接对所有边暴力跑Kruscal，肯定会T。

注意题目只要求我们求这个图的最小生成树。用 Kruskal 求最小生成树时，用到的核心思想是并查集判断联通。我们考虑借助这个思想，跳过建图的过程，直接求最小生成树。

由于每次给定了我们很多点，并要求其中每个点之间都建一条给定权值的边。所以建一个集合的边，就相当于把该集合全都并到一个并查集里。

我们按照边权从小到大给输入的集合排个序，这样每个集合中的点第一次联通建的就一定是权值最小的边。我们每在连通块中加入一个新节点，就在一个累加器中加入该边的权值。当图第一次联通时，输出该累加器即可。这一部分除了存边的形式，其他都和 Kruskal 算法一样。

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
signed main() {

    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m;
    std::vector<int> k(m), c(m);
    std::vector a(m, std::vector<int>());
    for (int i = 0; i < m; i++) {
        std::cin >> k[i] >> c[i];
        a[i].resize(k[i], 0);
        for (auto& j : a[i]) {std::cin >> j; --j;}
    }
    std::vector<int> ord(m);
    std::iota(ord.begin(), ord.end(), 0);
    ranges::sort(ord, [&](int i, int j){return c[i] < c[j];});
    
    DSU dsu(n);
    i64 ans = 0;
    int cnt = 0;
    for (auto& i : ord) {
        for (int j = 1; j < k[i]; j++) if (not dsu.same(a[i][0], a[i][j])) {//随便选一个，这里我选的第0个
            dsu.merge(a[i][0], a[i][j]); ans += c[i]; cnt += 1;
        }
    }
    
    std::cout << (cnt == n - 1 ? ans : -1) << '\n';

    return 0;
}

F - Estimate Order

https://atcoder.jp/contests/abc352/tasks/abc352\_f

好难的状压

  • 有一个长度为 (N) 的排列 (A_i)，现在给定若干对关系，每对关系形如 ((x,y,c))，表示 (A_x-A_y=c)。
  • 对于所有 (i\in[1,N])，若 (A_i) 只有一种取值，输出 (A_i)，否则输出 (-1)。
  • (1\le N\le 16)，保证至少一种合法的序列 (A_i)。

容易想到用并查集处理有哪些 (A_i) 是有关联的，具体来说，存储 (rank_{i,j}) 表示若 (A_j=A_i+rank_{i,j})，不存在则为 (0)，这个在并查集时可以暴力维护，复杂度 (O(N^2))。

那么处理出相关联的集合后应该怎么做呢？

注意到 (N\le 16)，那么容易想到状态压缩，可以用一个 (16) 位的整数存储某集合 (S) 中数的相对大小（比如 (S_i={i_1,i_2,i_3,i_4})，其中 (A_{i_2}=A_{i_1}+3,A_{i_3}=A_{i_1}+4,A_{i_4}=A_{i_1}+15)，那么可以用 (B_i=1000000000011001) 表示 (S)），然后问题就变成了若干个数 (1) 的总数为 (n)，将它们每个左移若干位，使得或起来恰好为 (2^N-1)，且不相交。那么若 (B_i) 有且仅有一种左移的位数能在加入其它数后变成一个合法的解，就说明 (S_i) 中所有元素均有唯一解，并且 (A_i) 的具体值是容易得到的。

于是容易想到 dp，具体来说，设 (f_{i,msk}) 表示将前 (i) 个数合并起来后能否得到 (msk)，转移比较简单，存储上一次塞了 (i-1) 的所有 (msk)，然后枚举 (B_i) 左移多少位从这些 (msk) 转移即可。

这样只能求出有无解（但是题目保证有解捏），看起来很蠢啊。但是容易发现这说明 (f_{N,2^N-1}) 的所有前驱都能在进行一定操作后变成一个合法的解，那么我们可以存储 (B_i) 的每种左移的位数能转移到哪些 (f_{i,msk})，再看有哪些左移位数所转移到的状态集合中有 (f_{N,2^N-1}) 的前驱，就能得到 (S_i) 有中的元素是否有唯一解了。

因为每个 (msk)​ 只会出现一次，所以其实可以把 (i)​ 这一维压掉，复杂度就是 (O(n2+n2n))​，非常可以接受。

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
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N, M; std::cin >> N >> M;

    //维护依赖关系构成的连通块
    std::vector<int> A(M), B(M), C(M);
    DSU dsu(N); for (int i = 0; i < M; i++) {std::cin >> A[i] >> B[i] >> C[i]; --A[i]; --B[i]; dsu.merge(A[i], B[i]);}

    std::vector g(N, std::vector<std::pair<int, int>>());//用依赖关系建边构成的图
    for (int i = 0; i < M; i++) {g[A[i]].emplace_back(B[i], -C[i]); g[B[i]].emplace_back(A[i], C[i]);}

    std::vector<int> block_masks, state_masks(N), shift(N);

    // 处理出每一个选手为最高排名时的连通块的所有信息
    for (int now = 0; now < N; now++) {
        std::vector<int> val(N, -1); val[now] = N;//当前是最高排名
        std::vector<int> block_points{now};
        //遍历整个连通块，更新所有点到当前起点的花费
        for (int i = 0; i < SZ(block_points); i++) for (auto&[to, delta] : g[block_points[i]]) if (val[to] == -1) {
            val[to] = val[block_points[i]] + delta; block_points.push_back(to);
        }

        int mn = N * 2; for (auto& x : block_points) {mn = std::min(mn, val[x]);}//维护出整个连通块的最小价值

        for (auto& x : block_points) {state_masks[now] |= (1 << (val[x] - mn));}//状态用所有点到最小花费的相对值来表示，并压缩
        shift[now] = val[now] - mn;//要左移的距离
        if (dsu.find(now) == now) {block_masks.push_back(state_masks[now]);}//是连通块的祖先，加入dp序列
    }

    for (int now = 0; now < N; now++) {
        std::vector<bool> dp(1 << N); dp[0] = true;
        bool skipped = false;
        for (auto& now_mask : block_masks) {
            if (not skipped and now_mask == state_masks[now]) {skipped = true; continue;}//其中一个状态是和自己重合的，跳过并只跳过一次
            std::vector<bool> ndp(1 << N);
            for (int mask = 0; mask < (1 << N); mask++) if (dp[mask]) {
                int now_state = now_mask;
                while (now_state < (1 << N)) {//左移当前状态更新状态
                    if ((mask & now_state) == 0) {ndp[now_state | mask] = true;}//只要不相交，即与为0，那么或起来的状态可以到达
                    now_state <<= 1;
                }
            }
            dp = ndp;
        }
        int now_state = state_masks[now];
        int add = 0;
        std::vector<int> res;
        while (now_state < (1 << N)) {
            int left = (1 << N) - 1 - now_state;
            if (dp[left]) {res.push_back(add + shift[now]);}//如果能到达左移后的位置
            now_state <<= 1; add += 1;
        }
        std::cout << (SZ(res) > 1 ? -1 : res.front() + 1) << " \n"[now == N - 1];
    }

    return 0;
}