题解 AT2568 【Lotus Leaves】

· · 题解

题目要求最少需要将多少个 o 改成 . ，可以使这个人无法从 S 到达 T 。很容易想到最小割。

由最小割等于最大流可以想到一个特别 naive 的想法：S 只连出边，T 只连入边，其它点向其能到达的点连边，然后跑网络流。

因为点与点之间连的边只是为了连通两个点，所以边权是 +\infty 。比较困难的是如何通过边权的限制实现每个点只割一次。

对于这种限制点权的网络流，一种简单的方法是把一个点拆成一个入点和一个出点，并且在入点和出点之间连一条流量为点权的边。所有以该点为终点的边全部连到它的入点，反之则连到它的出点。

这样连好后就可以跑网络流了，但是对于每个点，其在每一行内最多有 n 个可到达点，列也是如此，一共有 n^2 个点，最多有 n^3 条边，感觉 10^6 不太可过，考虑优化。

不难发现，对于同一行或者同一列的点，都是互相可达，那么其实不需要两两连边，只需要对于每行和列建一个辅助节点作为中转，即可把边数降到 n^2 级别。

最后的最大流就是所求答案，至于判断可行性，可以一开始就看 S 和 T 在不在同一行或同一列内，也可以看跑完网络流后是不是割了 +\infty 边。

代码如下：

#include <bits/stdc++.h>
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

char buf[1000000], *p1 = buf, *p2 = buf;
inline char gc() {
  if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
  return p1 == p2 ? EOF : *(p1++);
}
template <class T> inline void read(T &n) {
  n = 0; RI ch = gc(), f;
  while ((ch < '0' || ch > '9') && ch != '-') ch = gc();
  f = (ch == '-' ? ch = gc(), -1 : 1);
  while (ch >= '0' && ch <= '9') n = n * 10 + (ch ^ 48), ch = gc();
  n *= f;
}

int const MAXN = 105, INF = 0x7f7f7f7f;
struct Edges { int to, next, dis; } e[MAXN * MAXN * MAXN];
int head[MAXN * MAXN * MAXN], tot = 1;
int In[MAXN][MAXN], Out[MAXN][MAXN], cnt, S, T, Row[MAXN], Line[MAXN];
int dep[MAXN * MAXN * MAXN], cur[MAXN * MAXN * MAXN];
char s[MAXN][MAXN];
queue <int> q;

inline void addedge(int from, int to, int dis) {
  e[++tot] = (Edges){to, head[from], dis};
  head[from] = tot;
  e[++tot] = (Edges){from, head[to], 0};
  head[to] = tot;
}

bool Bfs() {
  memset(dep, 0, sizeof(dep));
  dep[S] = 1;
  q.push(S);
  while (!q.empty()) {
    int t = q.front(); q.pop();
    for (RI i = head[t]; i; i = e[i].next)
      if (!dep[e[i].to] && e[i].dis)
        dep[e[i].to] = dep[t] + 1, q.push(e[i].to);
  }
  if (!dep[T]) return 0;
  for (RI i = 1; i <= cnt; ++i) cur[i] = head[i];
  return 1;
}

int Dfs(int now, int res) {
  if (now == T || !res) return res;
  int sum = 0;
  for (RI i = cur[now]; i; i = e[i].next) {
    cur[now] = i;
    if (dep[e[i].to] == dep[now] + 1) {
      int d = Dfs(e[i].to, min(res, e[i].dis));
      if (d) {
        sum += d;
        res -= d;
        e[i].dis -= d;
        e[i ^ 1].dis += d;
      }
    }
  }
  return sum;
}

int Dinic() {
  int Maxflow = 0;
  while (Bfs())
    Maxflow += Dfs(S, INF);
  return Maxflow;
}

int main() {

#ifdef LOCAL
  FILEIO("a");
#endif

  int n, m; scanf("%d %d", &n, &m);
  for (RI i = 1; i <= n; ++i)
    scanf("%s", s[i] + 1);
  for (RI i = 1; i <= n; ++i) Row[i] = ++cnt;
  for (RI i = 1; i <= m; ++i) Line[i] = ++cnt;
  for (RI i = 1; i <= n; ++i)
    for (RI j = 1; j <= m; ++j) {
      if (s[i][j] == 'o') {
        In[i][j] = ++cnt, Out[i][j] = ++cnt;
        addedge(Out[i][j], Row[i], INF);
        addedge(Out[i][j], Line[j], INF);
        addedge(Row[i], In[i][j], INF);
        addedge(Line[j], In[i][j], INF);
        addedge(In[i][j], Out[i][j], 1);
      }
      if (s[i][j] == 'S') {
        S = ++cnt;
        addedge(S, Row[i], INF);
        addedge(S, Line[j], INF);  
      }
      if (s[i][j] == 'T') {
        T = ++cnt;
        addedge(Row[i], T, INF);
        addedge(Line[j], T, INF);
      }
    }
  int Maxflow = Dinic();
  if (Maxflow > n * m) puts("-1");
  else printf("%d\n", Maxflow);

  return 0;
}

// created by Daniel yuan