11/6
20:44
OI

[Lydsy1705月赛]棋盘上的守卫 [Kruskal]

费用流显然是不行的…不过根据网格图套路,我们可以建出一张行列为点的图来.

考虑如何表示方向.可以把一个点到另一个点的有向边,看作守卫了后面那个点的一行.要守卫所有行列,即每个点入度都为1,是外向树森林.

用Kruskal维护MST即可

#include <bits/stdc++.h>

const int N = 2e5 + 2333;

int n, m, fa[N], cir[N], tot;
long long ans;

struct Node {
  int x, y, c;
} e[N];

bool operator<(const Node &a, const Node &b) {
  return a.c < b.c;
}

int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n + m; ++i)
    fa[i] = i;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      scanf("%d", &e[++tot].c);
      e[tot].x = i, e[tot].y = n + j;
    }
  std::sort(e + 1, e + n * m + 1);
  for (int i = 1; i <= n * m; ++i) {
    int x = find(e[i].x), y = find(e[i].y);
    if (cir[x] && cir[y])
      continue;
    if (x == y)
      cir[x] = 1;
    else {
      fa[x] = y;
      cir[y] |= cir[x];
    }
    ans += e[i].c;
  }
  std::cout << ans << std::endl;
  return 0;
}