CF1630F

randrandmew · 2023-09-22 15:21:15 · 题解

不太一样的做法。好像要简洁一些。

如前人题解所说，一个点如果既有入度又有出度，它就寄了。

因为要删的是点，先拆点变成边。

然后再对每个点额外拆出两个点，记录入边和出边。结构如下图所示。

跑一下最小割就可以了。

连边部分的代码，其余是 dinic 板子。

    int n = read();
    vector<int> a(n);
    map<int, int> id;
    for (int i = 0; i < n; ++i) {
      a[i] = read();
      id[a[i]] = i;
    }
    int _S = 4 * n, _T = 4 * n + 1;
    flow<int> flow(_T + 1, _S, _T);
    for (int i = 0; i < n; ++i) {
      flow.add(_S, i, 1);
      flow.add(i + n, i + 2 * n, 1);
      flow.add(i + 3 * n, _T, 1);
    }
    for (int i = 0; i < n; ++i) {
      for (int x : d[a[i]]) {
        if (!id.count(x))
          continue;
        int v = id[x];
        flow.add(i, v + n, 1);
        flow.add(i + 2 * n, v + 3 * n, 1);
      }
    }
    i64 ans = flow.get();
    cout << ans << '\n';