最大流的一个基本算法就是Ford-Fulkerson，基本的思路是：每次寻找一条增广路，记下增广路上最小的可改进量，并改进这条增广路，如此循环直到不存在增广路。

可以发现，Ford-Fulkerson有点浪费时间，SAP应用标号思想进行优化。另外对于单流增广，它必须找到一条完整的增广路之后再进行增广，如果存在一条岔路，那么它必须分作好几次才能做完。因此多流增广就有了：对于一个节点，在其可增广范围内对其相邻节点递归增广。

网络流的题目在构图的时候有个小技巧，原先需要使用剩余网络，必须有两张图存储。而实际应用中，只要每一条有向边都有一条跟它对应的反向边，且这两条边的流量值和等于容量限制即可。这样只要在一张图中存储即可，省去不少麻烦。自然，改进这条路的时候，将一条边上的流量+Delta，另一条边-Delta。

关于Ford-Fulkerson和SAP的基本思想可以参考附件的两个课件。下面贴出来几题最大流的题目，详细的Ford-Fulkerson和SAP实现见程序，可以参考注释。

[PKU1273]Drainage Ditches

赤裸裸的网络流，下面的程序是Ford-Fulkerson算法。

#include <iostream>
#include <cstring>
using namespace std;

int n, m, MaxFlow, _top, q[402], last[402];
bool s[402];
struct Links
{
  int v, f;
  Links *next, *op;
} h[402];
Links* header[402], *Path[402];
inline Links* join(const int x, const int y, const int f, Links *op = NULL)
{
  h[++_top].v = y;
  h[_top].f = f;
  h[_top].next = header[x];
  header[x] = h+_top;
  if (op)
  {
    h[_top].op = op;
    op->op = &h[_top];
  }
  return &h[_top];
}
bool fulkerson()
{
  memset(s, 0, sizeof(s));
  int head = 0, tail = 0, u;
  /* 先进行广搜寻找一条增广路，将路径记录在Path[] */
  Links* v;
  q[++tail] = 1, s[1] = true, last[tail] = 0;
  while (head < tail && !s[m])   {     u = q[++head];     v = header[u];     while (v != NULL)     {       if (!s[v->v] && v->f)
      {
        s[v->v] = true;
        last[++tail] = head;
        q[tail] = v->v;
        Path[tail] = v;
        if (v->v == m) break;
      }
      v = v->next;
    }
  }
  if (!s[m]) return false;
  /* 按照Path[]的路径寻找这条增广路上的最小可改进量 */
  int Delta = 0x7FFFFFFF;
  u = tail;
  while (last[u])
  {
    Delta = min(Delta, Path[u]->f);
    u = last[u];
  }
  /* 修改各边流量 */
  u = tail;
  while (last[u])
  {
    Path[u]->f -= Delta;
    Path[u]->op->f += Delta;
    u = last[u];
  }
  MaxFlow += Delta;
  return true;
}
int main()
{
  ios::sync_with_stdio(false);
  while (cin >> n >> m)
  {
    _top = 0;
    MaxFlow = 0;
    memset(header, 0, sizeof(header));

    for (int i = 0, st, ed, c; i < n; ++i)     {       cin >> st >> ed >> c;
      join(ed, st, 0, join(st, ed, c));
    }
    while (fulkerson());
    cout << MaxFlow << endl;
  }
}

[PKU1459]Power Network

这题需要简单的构图。从源点S连Np条边到发电站，接着用m条边连接发电站和客户，最后用Nc条边连接客户和源点。然后做一遍最大流即可。下面这题用单流SAP实现（建议看下一题的多流SAP，程序比这个简洁而且速度更快）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Links
{
  int v, f;
  Links *Next, *op;
} h[21012];
int _LinkSize, n, np, nc, m, MaxFlow, S, T, dist[102], cd[102];
bool FoundAUG;
Links* Header[102];
inline Links* join(const int x, const int y, const int w, Links* op = NULL)
{
  Links* node = &h[_LinkSize++];
  node->v = y;
  node->f = w;
  node->op = op;
  node->Next = Header[x];
  Header[x] = node;
  if (op)
    op->op = node;
  return node;
}
int SAP(const int u, const int Delta)
{
  if (u == T)
  {
    FoundAUG = true; /* FoundAUG是找到增广路的标志 */
    return Delta;
  }
  int MinDist = n, sum = 0;
  Links *v = Header[u];
  while (v)
  {
    if (dist[u]-1 == dist[v->v] && v->f)
    {
      sum += SAP(v->v, min(Delta, v->f));
      if (dist[S] >= n) return sum;
      if (FoundAUG) break; /* 找到增广路就不必再找了，退出进行改进 */
    }
    if (v->f)
      MinDist = min(MinDist, dist[v->v]);
    v = v->Next;
  }
  if (!FoundAUG) /* 没找到增广路进行重标号 */
  {
    --cd[dist[u]];
    if (!cd[dist[u]])
      dist[S] = n; /* GAP优化 */
    dist[u] = MinDist+1;
    ++cd[dist[u]];
  }
  else /* 找到了就更新 */
  {
    v->f -= sum;
    v->op->f += sum;
  }
  return sum;
}
int main()
{
  while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF)
  {
    S = n, T = n+1, _LinkSize = 0, MaxFlow = 0;
    memset(Header, 0, sizeof(Header));
    memset(dist, 0 , sizeof(dist));
    memset(cd, 0, sizeof(cd));
    for (int i = 0, x, y, w; i < m; ++i)
    {
      scanf("%*[^(](%d,%d)%d", &x, &y, &w);
      join(y, x, 0, join(x, y, w));
    }
    for (int i = 0, y, w; i < np; ++i)
    {
      scanf("%*[^(](%d)%d", &y, &w);
      join(y, S, 0, join(S, y, w));
    }
    for (int i = 0, x, w; i < nc; ++i)
    {
      scanf("%*[^(](%d)%d", &x, &w);
      join(T, x, 0, join(x, T, w));
    }

    n += 2;
    cd[0] = n;
    while (dist[S] < n)
    {
      FoundAUG = false;
      MaxFlow += SAP(S, 0x3FFFFFFF);
    }
    printf("%dn", MaxFlow);
  }
}

[PKU1698]Alice’s Chance

首先是构图。由源S分别连接容量为d[i]的边到第i个电影。接着把几个MaxW个星期拆成MaxW7个点表示每一天，如果第i部电影可以在第x天拍摄的话，那么就连一条容量为1的边到x天。最后把MaxW7天分别连容量为1的边到汇点T。做一次最大流，如果最大流=Sum{d[i]}，那么就Yes，否则No。这题的程序是我最满意的，推荐看这题的程序。SAP写的是多流增广。

#include <iostream>
#include <cstring>
using namespace std;

struct Links
{
  int v, f;
  Links *op, *Next;
} h[30000];
int TestData, n, D, W, MaxW, _LinkSize, S, T, MaxFlow, DistCounter[2000], Dist[2000], week[7];
Links *Header[2000];
inline Links* AddEdge(const int x, const int y, const int f, Links *op = NULL)
{
  Links *node = &h[_LinkSize++];
  node->v = y;
  node->f = f;
  node->op = op;
  node->Next = Header[x];
  Header[x] = node;
  if (op)
    op->op = node;
  return node;
}
int SAP(const int u, const int Delta)
/* Delta是硬性限制，即从u点出发进行增广最多能增广多少，这受到u前面边的限制 */
{
  if (u == T)
    return Delta;
/* 到达汇点返回当前最大可改进量Delta */
  int MinDist = n, sum = 0; /* sum记录从u点出发已经改进了多少 */
  for (Links *v = Header[u]; v; v = v->Next)
  {
    if (Dist[u]-1 == Dist[v->v] && v->f)
    {
      int d = SAP(v->v, min(Delta-sum, v->f));
/* 沿着边v进行增广。从v->v这个点出发最多能改进的流量受到v这条边的可改进量和u点的限制 */
      sum += d;
      v->f -= d;
      v->op->f += d;
/* 马上更新v和其对应边 */
      if (Dist[S] >= n || sum == Delta)
        return sum;
    }
    if (v->f)
      MinDist = min(MinDist, Dist[v->v]);
  }
  if (sum == 0) /* 未找到增广路进行重标号 */
    if (!--DistCounter[Dist[u]])
      Dist[S] = n;
    else
      ++DistCounter[Dist[u] = MinDist+1];
  return sum;
}
int main()
{
  ios::sync_with_stdio(false);
  cin >> TestData;
  while (TestData--)
  {
    S = 0, D = 0, _LinkSize = 0, MaxFlow = 0, MaxW = 0;
    memset(Header, 0, sizeof(Header));
    memset(Dist, 0 , sizeof(Dist));
    memset(DistCounter, 0, sizeof(DistCounter));
    cin >> n;
    for (int i = 1, d; i > week[j];
      cin >> d >> W;
      AddEdge(i, S, 0, AddEdge(S, i, d));
      D += d;
      for (int k = 0; k != W; ++k)
        for (int j = 0; j != 7; ++j)
          if (week[j])
            AddEdge(1+n+k*7+j, i, 0, AddEdge(i, 1+n+k*7+j, 1));
      MaxW = max(MaxW, W);
    }
    T = n+MaxW*7+1;
    for (int k = 0; k != MaxW; ++k)
      for (int j = 0; j != 7; ++j)
        AddEdge(T, 1+n+k*7+j, 0, AddEdge(1+n+k*7+j, T, 1));

    DistCounter[0] = n = T-S+1;
    while (Dist[S] < n)
      MaxFlow += SAP(S, 0x3FFFFFF);

    cout << (MaxFlow == D ? "Yes" : "No") << endl;
  }
}

总结

其实熟悉了算法后，最大流的题目难点转移到了构图上面。只要图构造出来了，SAP套进去答案就出来了。

QuarterGeek

Lequn Chen (abcdabcd987) 's Blog

最大流3题

[PKU1273]Drainage Ditches

[PKU1459]Power Network

[PKU1698]Alice’s Chance

总结

Comments