最大流

1. EK算法

这个算法效率谈不上多高，写上来主要是防止出现什么必须得用它的情况

  1. //P3376
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. struct Edge {
  5.     int from, to, flow;
  6.     Edge(int u, int v, int f) : from(u), to(v), flow(f) {}
  7. };
  8. const int N = 210;
  9. int n, m, s, t;
  10. vector<Edge> edges;
  11. vector<int> G[N];
  12. int vis[N], inch[N], pre[N];
  13. long long maxflow;
  14. void addEdge(int from, int to, int flow) {
  15.     edges.push_back((Edge){from, to, flow});
  16.     G[from].push_back(edges.size() - 1);
  17. }
  18. bool bfs() {
  19.     memset(vis, 0, sizeof(vis));
  20.     queue<int> q;
  21.     q.push(s), vis[s] = 1, inch[s] = 0x3f3f3f3f;
  22.     while (!q.empty()) {
  23.         int x = q.front(); q.pop();
  24.         if (x == t) return true;
  25.         for (int i = 0; i < G[x].size(); ++i) {
  26.             Edge &e = edges[G[x][i]];
  27.             int to = e.to;
  28.             if (vis[to] || e.flow == 0)
  29.                 continue;
  30.             inch[to] = min(inch[x], e.flow);
  31.             pre[to] = G[x][i];
  32.             q.push(to), vis[to] = 1;
  33.         }
  34.     }
  35.     return false;
  36. }
  37. void update() {
  38.     int x = t;
  39.     while (x != s) {
  40.         int i = pre[x];
  41.         edges[ i ].flow -= inch[t];
  42.         edges[i^1].flow += inch[t];
  43.         x = edges[i].from;
  44.     }
  45.     maxflow += inch[t];
  46. }
  47. int main()
  48. {
  49.     scanf("%d%d%d%d", &n, &m, &s, &t);
  50.     for (int i = 1; i <= m; ++i) {
  51.         int from, to, flow;
  52.         scanf("%d%d%d", &from, &to, &flow);
  53.         addEdge(from, to, flow);
  54.         addEdge(to, from, 0);
  55.     }
  56.     while (bfs()) update();
  57.     printf("%lld\n", maxflow);
  58.     return 0;
  59. }

2. Dinic 算法

基于EK算法的优化，效率很高，基本上不太可能被卡。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 210, M = 5010 * 2, INF = 1 << 30;
  4. int n, m, s, t;
  5. //
  6. int tot, head[N], Next[M], ver[M], Flow[M];
  7. void addEdge(int u, int v, int f) {
  8.     ver[++tot] = v, Flow[tot] = f;
  9.     Next[tot] = head[u], head[u] = tot;
  10. }
  11. //
  12. int d[N];
  13. queue<int> q;
  14. bool bfs()
  15. {
  16.     memset(d, 0, sizeof(d));
  17.     while (!q.empty()) q.pop();
  18.     q.push(s), d[s] = 1;
  19.     while (!q.empty()) {
  20.         int x = q.front(); q.pop();
  21.         if (x == t) return true;
  22.         for (int i = head[x]; i; i = Next[i]) {
  23.             int to = ver[i];
  24.             if (!d[to] && Flow[i])
  25.                 q.push(to), d[to] = d[x] + 1;
  26.         }
  27.     }
  28.     return false;
  29. }
  30. //
  31. int Dinic(int x, int flow) {
  32.     if (x == t) return flow;
  33.     int rest = flow;
  34.     for (int i = head[x]; i; i = Next[i]) {
  35.         int to = ver[i];
  36.         if (Flow[i] && d[to] == d[x] + 1) {
  37.             int k = Dinic(to, min(rest, Flow[i]));
  38.             if (!k) d[to] = 0;
  39.             Flow[i] -= k, Flow[i^1] += k;
  40.             rest -= k;
  41.             if (rest == 0) break;
  42.         }
  43.     }
  44.     if (rest == flow) d[x] = 0;
  45.     return flow - rest;
  46. }
  47. int main()
  48. {
  49.     //input
  50.     scanf("%d%d%d%d", &n, &m, &s, &t);
  51.     tot = -1;
  52.     for (int i = 1; i <= m; ++i) {
  53.         int from, to, flow;
  54.         scanf("%d%d%d", &from, &to, &flow);
  55.         addEdge(from, to, flow);
  56.         addEdge(to, from,  0  );
  57.     }
  58.     //solve
  59.     long long maxflow = 0;
  60.     int flow;
  61.     while (bfs())
  62.         while (flow = Dinic(s, INF)) maxflow += flow;
  63.     //output
  64.     printf("%lld\n", maxflow);
  65.     return 0;
  66. }

费用流

最小费用最大流

和 EK 算法类似，不过把增广路的 BFS 换成了 SPFA

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define LL long long
  4. const int N = 5010, M = 100010;
  5. const LL INF = 0x3f3f3f3f3f3f3f3f;
  6. int n, m, s, t;
  7. LL maxflow, ans;
  8. int tot, Head[N], Next[M], ver[M];
  9. LL Flow[M], Cost[M];
  10. void addEdge(int u, int v, LL flow, LL cost) {
  11.     ver[++tot] = v, Flow[tot] = flow, Cost[tot] = cost;
  12.     Next[tot] = Head[u], Head[u] = tot;
  13. }
  15. LL d[N], incf[N];
  16. int pre[N], vis[N];
  17. bool SPFA() {
  18.     queue<int> q;
  19.     memset(d, 0x3f, sizeof(d));
  20.     memset(vis, 0, sizeof(vis));
  21.     q.push(s), d[s] = 0, vis[s] = 1;
  22.     incf[s] = INF;
  23.     while (!q.empty()) {
  24.         int x = q.front(); q.pop();
  25.         vis[x] = 0;
  26.         for (int i = Head[x]; i; i = Next[i]) {
  27.             if (!Flow[i]) continue;
  28.             int to = ver[i];
  29.             if (d[to] > d[x] + Cost[i]) {
  30.                 d[to] = d[x] + Cost[i];
  31.                 incf[to] = min(incf[x], Flow[i]);
  32.                 pre[to] = i;
  33.                 if (!vis[to]) vis[to] = 1, q.push(to);
  34.             }
  35.         }
  36.     }
  37.     return (d[t] != INF);
  38. }
  39. void update() {
  40.     int x = t;
  41.     while (x != s) {
  42.         int i = pre[x];
  43.         Flow[i] -= incf[t], Flow[i^1] += incf[t];
  44.         x = ver[i^1];
  45.     }
  46.     maxflow += incf[t];
  47.     ans += d[t] * incf[t];
  48. }
  50. int main()
  51. {
  52.     scanf("%d%d%d%d", &n, &m, &s, &t);
  53.     tot = 1;
  54.     for (int i = 1; i <= m; ++i) {
  55.         int u, v;
  56.         LL flow, cost;
  57.         scanf("%d%d%lld%lld", &u, &v, &flow, &cost);
  58.         addEdge(u, v, flow, cost);
  59.         addEdge(v, u,  0 , -cost);
  60.     }
  61.     while (SPFA()) update();
  62.     printf("%lld %lld", maxflow, ans);
  63.     return 0;
  64. }

最大费用最大流

将费用取反后放进图里跑，得到的结果的相反数就是答案。