2023级算法E4练习赛

2023级算法第四次上级赛

A 2024-妮妮与自来水厂

思路分析

Hint里直接说明了，本题考察的是网络流基本模型，具体模板参考https://oi-wiki.org/graph/flow/max-flow/即可，建议使用Dinic算法

AC代码

#include<bits/stdc++.h>
#define N 101
#define M 10001 // the double number of original edges, which involves the reverse edge of each.
#define INF 100000000000000000ll
using namespace std;

typedef struct MF {
  struct edge {
    int v, nxt;
    long long cap, flow;
    // vejex next_edge capacity flow
  } e[M];

  int fir[N], cnt = 0; // cnt: the number of edges; fir[n]: first edge to consider;

  int n, S, T; // number of v; source; target
  long long maxflow = 0;
  int dep[N], cur[N];

  void init() {
    memset(fir, -1, sizeof fir);
    cnt = 0;
  }

  // fir实现当前弧优化
  void addedge(int u, int v, long long w) {
    e[cnt] = {v, fir[u], w, 0};
    fir[u] = cnt++;
    e[cnt] = {u, fir[v], 0, 0}; // reverse edge
    fir[v] = cnt++;
  }

  bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof(int) * (n + 1));

    dep[S] = 1;
    q.push(S);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int i = fir[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if ((!dep[v]) && (e[i].cap > e[i].flow)) {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return dep[T];
  }

  long long dfs(int u, long long flow) {
    if ((u == T) || (!flow)) return flow;

    long long ret = 0;
    for (int& i = cur[u]; ~i; i = e[i].nxt) {
      int v = e[i].v, d;
      if ((dep[v] == dep[u] + 1) &&
          (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {
        ret += d;
        e[i].flow += d;
        e[i ^ 1].flow -= d;
        if (ret == flow) return ret;
      }
    }
    return ret;
  }

  void dinic() {
    while (bfs()) {
      memcpy(cur, fir, sizeof(int) * (n + 1));
      maxflow += dfs(S, INF);
    }
  }
} mf;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m, s, t;
        scanf("%d%d%d%d", &n, &m, &s, &t);
        mf network;
        network.init();
        network.S = s;
        network.T = t;
        network.n = n;

        for (int i = 0; i < m; i++) {
            int u, v;
            long long w;
            scanf("%d%d%lld", &u, &v, &w);
            network.addedge(u, v, w);
        }

        network.dinic();
        printf("%lld\n", network.maxflow);
    }
    return 0;
}