最大流构图小结

被最大流虐了一个星期才做出了五题，效率有点非常的低……既然如此，那就写点总结来弥补吧。

先讲讲构图上的常用技巧：

S-T直接构图

有的题目非常非常的水，水到几乎题目就跟你讲好如何构图了，并且点的数量也少，那就毫不犹豫地按照题目的要求从源点S到汇点T构图。如：上次《最大流3题》里面的pku1459、pku1273

*根据性质优化

有些题目很容易根据题目意思构出朴素的图，但与上面S-T直接构图不同的是，这种朴素的构图法构出来的图点数和边数很大，比方说1000^{2，那根据网络流算法的最差O(n}3)的复杂度，超时是必定的了。这个时候就得根据朴素的图的特殊性质来进行缩点。

比方说pku1149，根据朴素的构图方法会产生约100,000个点，进行如下优化：

如果几个节点的来源完全相同，则可以把它们合成一个。
如果几个节点的去向完全相同，则可以把它们合成一个。
如果从u到v有一条容量为∞的边，并且v除了u以外没有别的流量来源，则可以把这它们合并成一个。

如此优化后可以整理思路重新构图，即可得到只有n+2个点也就是102个点的图。

差值建图

有些题目的节点之间没有直接的联系，但是有差值的联系。比方说pku1637，判定混合图欧拉回路，重点就放在可以自由改变方向的无向边上，如果一个节点的(出度-入度)不为0，则说明需要改变(出度-入度)/2条无向边的方向，根据这一特点构图即可找到突破口。

拆点

拆点这个方法可谓是非常好用。对于有两个考虑对象的题目，可以考虑把点拆掉。也就是说，根据第一个考虑对象构造S到i的边容量，根据第二个考虑对象构造i’到T的边容量，再根据单个节点的限制将i和i’连接起来。

比如pku2391，将每个节点拆成i和i’，(S,i)的容量为房子i原来牛的个数，(i’,T)的容量为房子i可以容纳的牛数，由于牛可以随意乱跑而不会把房子撑破，所以(i,i’)=∞。

又如pku3281，(S,food)为食物供给，(drink,T)为饮料供给，将奶牛i拆成i和i’，如果愿意吃food，那么连边(food,i)，同理如果爱喝drink，那么连边(i’,drink)。

限流

有些拆点的题目单个个体是有限制的，比方说pku3281中一只牛最多只能有一份食物一份饮料，那么连(i,i’)容量为1的边，以防某头牛多吃食物或者多喝饮料。

容量为1的边常用来来限制流量。

容量为∞的边常用来表示流量不限。

满流判定

满流判定一般是用在可以转化成为判定性问题的题目上，多次建图，建图时把从源点出来的边的容量加起来得到FullFlow，如果最后算出来的最大流MaxFlow==FullFlow，那就满流。

如pku1637，因为欧拉回路要求每个点入读=出度，因此最后必须把所有方向不对的无向边改对，也就是必须满流。

又如pku2699，如果MaxFlow==n*(n-1)/2那么当前Strong Kings的分配方案就是可行的。

二分和枚举

有的题目其边的存在或者容量与某些变量有关系，比方说和时间t有关，如果满足单调性就可以二分时间t进行构图，每次转换成判定性问题即可。

如pku2391，二分时间多次建图再判定即可。

当然，如果数据范围小或者不满足单调性，那枚举也是可以的。如pku2699中n<=10，完全没有二分的必要。

下面就对近期做的几题做一下单题题解。所有题目的详细解答都可以在[网络流建模汇总][Edelweiss].pdf中找到。

PKU1149：朴素构图+优化

因为顾客是按顺序一个一个来的，所以有朴素想法：

n个顾客就有n轮交易，每轮交易有m个猪圈和1个人。
从S到第一轮的每一个猪圈连容量为猪圈初始猪的数量的边。
每个顾客连一条边到T，容量为购买上限。
某一轮中，若顾客有猪圈i钥匙那就从该轮猪圈i节点连一条∞的边到顾客。
除了最后一轮以外，每一轮的猪圈i连向下一轮的猪圈i，容量∞，表示猪可以剩下。
最后一轮除外，从每一轮被打开的所有猪圈到下一轮的同样这些猪圈，两两之间都要连一条边，表示它们之间可以任意流通。

根据如下性质优化：

如果几个节点的来源完全相同，则可以把它们合成一个。
如果几个节点的去向完全相同，则可以把它们合成一个。
如果从u到v有一条容量为∞的边，并且v除了u以外没有别的流量来源，则可以把这它们合并成一个。

也就得到新的构图方法：

每个顾客分别用一个结点来表示。
对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。
对于每个猪圈，假设有n个顾客打开过它,则对所有整数i∈[1, n)，从该猪圈的第i个顾客向第i+1个顾客连一条边，容量为∞。
从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

const int INF(1<<30);
struct Edge
{
  int v, f;
  Edge *Next, *op;
} g[102*1000*2];
int EdgeSize, MaxFlow, n, m, S, T, PigHouse[1000], Want[100], Dist[102], DistCounter[102];
bool a[100][1000];
Edge* Header[102];
Edge* AddEdge(const int x, const int y, const int f, Edge* const op = NULL)
{
  Edge* node = g+(EdgeSize++);
  node->v = y;
  node->f = f;
  node->Next = Header[x];
  node->op = op;
  Header[x] = node;
  if (op != NULL)
    op->op = node;
  return node;
}
int SAP(const int u, const int Delta)
{
  if (u == T)
    return Delta;
  int sum = 0, MinDist = n;
  for (Edge* e = Header[u]; e; e = e->Next)
  {
    if (Dist[u]-1 == Dist[e->v] && e->f > 0)
    {
      int sap = SAP(e->v, std::min(Delta-sum, e->f));
      e->f -= sap;
      e->op->f += sap;
      sum += sap;
      if (sum == Delta || Dist[S] >= n)
        return sum;
    }
    if (e->f > 0)
      MinDist = std::min(MinDist, Dist[e->v]);
  }
  if (!sum)
    if (!--DistCounter[Dist[u]])
      Dist[S] = n;
    else
      ++DistCounter[Dist[u] = MinDist+1];
  return sum;
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin >> m >> n;
  for (int i = 0; i != m; ++i)
    cin >> PigHouse[i];
  for (int i = 0, count; i != n; ++i)
  {
    cin >> count;
    for (int j = 0, x; j != count; ++j)
    {
      cin >> x;
      a[i][x-1] = true;
    }
    cin >> Want[i];
  }
  S = n, T = n+1;
  for (int i = 0; i != m; ++i)
  {
    int last = S;
    for (int j = 0; j != n; ++j)
      if (a[j][i])
      {
        int f = last == S ? PigHouse[i] : INF;
        AddEdge(j, last, 0, AddEdge(last, j, f));
        last = j;
      }
  }
  for (int j = 0; j != n; ++j)
    AddEdge(T, j, 0, AddEdge(j, T, Want[j]));

  DistCounter[0] = n = n+2;
  while (Dist[S] < n)
    MaxFlow += SAP(S, INF);
  cout << MaxFlow;
}

PKU1637：差值构图+满流判定

求混合图欧拉回路。混合图存在欧拉回路的条件是：规定无向边方向后，每个点入度=出度。因此我们可以先随意将无向边定向，统计每个点出入度之差，如果有差为奇数的点，则必然不存在欧拉回路。

假设每个点入度-出度/2为x，那么对于每个点只要将x条边改方向就可以使其出入度差为0。那么改哪些边呢？显然有向边无须考虑，从图中删去，根据原来无向边的定向构图，边的容量为1。对于入>出的点 u，连接边(u, t)，容量为 x；对于出>入的点 v，连接边(s, v)，容量为 -x。

如果能满流，也就是能改变所有不符合要求的无向边，使得每个点入度=出度，那么就存在欧拉回路。

#include <iostream>
#include <cstring>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;

struct Edge
{
  int v, f;
  Edge *Next, *op;
} g[1000*1000];
int TestCase, LinkSize, n, m, S, T, MaxFlow, road[1000][3], indeg[200], oudeg[200], Dist[202], DistCounter[202];
Edge* Header[202];
Edge* AddEdge(const int x, const int y, const int f, Edge* const op = NULL)
{
  Edge* node = g+(LinkSize++);
  node->v = y;
  node->f = f;
  node->op = op;
  node->Next = Header[x];
  Header[x] = node;
  if (op != NULL)
    op->op = node;
  return node;
}
int SAP(const int u, const int Delta)
{
  if (u == T)
    return Delta;
  int sum = 0, MinDist = n;
  for (Edge* e = Header[u]; e; e = e->Next)
  {
    if (Dist[u]-1 == Dist[e->v] && e->f > 0)
    {
      int d = SAP(e->v, std::min(Delta-sum, e->f));
      sum += d;
      e->f -= d;
      e->op->f += d;
      if (Dist[S] >= n || sum == Delta)
        return sum;
    }
    if (e->f > 0)
      MinDist = std::min(MinDist, Dist[e->v]);
  }
  if (!sum)
    if (!--DistCounter[Dist[u]])
      Dist[S] = n;
    else
      ++DistCounter[Dist[u] = MinDist+1];
  return sum;
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin >> TestCase;
  for (; TestCase; --TestCase)
  {
    memset(indeg, 0, sizeof(indeg));
    memset(oudeg, 0, sizeof(oudeg));
    memset(Header, 0, sizeof(Header));
    memset(Dist, 0, sizeof(Dist));
    memset(DistCounter, 0, sizeof(DistCounter));
    LinkSize = 0;

    cin >> n >> m;
    for (int i = 0; i != m; ++i)
    {
      cin >> road[i][0] >> road[i][1] >> road[i][2];
      if (road[i][0] == road[i][1])
        continue;
      --road[i][0], --road[i][1];
      ++oudeg[road[i][0]], ++indeg[road[i][1]];
    }
    bool exist = true;
    for (int i = 0; i != n; ++i)
      if ((indeg[i]-oudeg[i])%2)
      {
        exist = false;
        break;
      }
    if (!exist)
    {
      cout << "impossible" << endl;
      continue;
    }

    for (int i = 0; i != m; ++i)
      if (!road[i][2])
        AddEdge(road[i][1], road[i][0], 0, AddEdge(road[i][0], road[i][1], 1));
    S = n, T = n+1;
    int FullFlow = 0;
    for (int i = 0; i != n; ++i)
      if (indeg[i] > oudeg[i])
        AddEdge(T, i, 0, AddEdge(i, T, (indeg[i]-oudeg[i])>>1));
      else if (indeg[i] < oudeg[i])
      {
        AddEdge(i, S, 0, AddEdge(S, i, (oudeg[i]-indeg[i])>>1));
        FullFlow += (oudeg[i]-indeg[i])>>1;
      }
    DistCounter[0] = n = n+2;
    MaxFlow = 0;
    while (Dist[S] < n)
      MaxFlow += SAP(S, 0x3FFFFFFF);

    cout << (MaxFlow == FullFlow ? "possible" : "impossible") << endl;
  }
}

PKU2391：拆点+二分答案

Floyd计算两点间最短距离d[i][j]，也就是最短转移时间。接下来，二分时间T，将i拆成i和i’两点，连边(S, i, Ai)，(i’, T, Bi)，如果d[i][j]<=T，那么连边(i, j’, ∞)。

#include <cstdio>
#include <cstring>
#include <algorithm>

const long long INF64(0x3F3F3F3F3F3F3F3F);
const int INF(0x3F3F3F3F);
struct Edge
{
  int v;
  long long f;
  Edge *Next, *op;
} g[1000*1000];
Edge* Header[500];
int n, m, Nodes, LinkSize, S, T, Dist[500], DistCounter[500], data[500][2];
long long FullFlow, d[500][500];
Edge* AddEdge(const int x, const int y, const long long f = 0, Edge* const op = NULL)
{
  Edge* const node = g+(LinkSize++);
  node->v = y;
  node->f = f;
  node->op = op;
  node->Next = Header[x];
  Header[x] = node;
  if (op != NULL)
    op->op = node;
  return node;
}
long long SAP(const int u, const long long Delta)
{
  if (u == T)
    return Delta;
  long long sum = 0;
  int MinDist = Nodes;
  for (Edge* e = Header[u]; e; e = e->Next)
  {
    if (Dist[u]-1 == Dist[e->v] && e->f > 0)
    {
      long long d = SAP(e->v, std::min(Delta-sum, e->f));
      sum += d;
      e->f -= d;
      e->op->f += d;
      if (Dist[S] >= Nodes || sum == Delta)
        return sum;
    }
    if (e->f > 0)
      MinDist = std::min(MinDist, Dist[e->v]);
  }
  if (!sum)
    if (!--DistCounter[Dist[u]])
      Dist[S] = Nodes;
    else
      ++DistCounter[Dist[u] = MinDist+1];
  return sum;
}
long long MaxFlow(const long long mid)
{
  memset(Dist, 0, sizeof(Dist));
  memset(DistCounter, 0, sizeof(DistCounter));
  memset(Header, 0, sizeof(Header));
  LinkSize = 0;
  for (int i = 0; i != n; ++i)
  {
    AddEdge(i+1, S, 0, AddEdge(S, i+1, data[i][0]));
    AddEdge(T, n+i+1, 0, AddEdge(n+i+1, T, data[i][1]));
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (d[i][j] <= mid)
        AddEdge(n+j, i, 0, AddEdge(i, n+j, INF64));

  DistCounter[0] = Nodes;
  long long flow = 0;
  while (Dist[S] < Nodes)
    flow += SAP(S, INF);
  return flow;
}
int main()
{
  memset(d, 0x3F, sizeof(d));
  scanf("%d%d", &n, &m);
  S = 0, T = (n<<1)+1;
  for (int i = 1; i <= n; ++i)
    d[i][i] = 0;
  for (int i = 0; i != n; ++i)
  {
    scanf("%d%d", &data[i][0], &data[i][1]);
    FullFlow += data[i][0];
  }
  for (int i = 0, a, b, x; i != m; ++i)
  {
    scanf("%d%d%d", &a, &b, &x);
    d[a][b] = d[b][a] = std::min(d[a][b], static_cast<long long>(x));
  }
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        d[i][j] = std::min(d[i][j], d[i][k]+d[k][j]);

  Nodes = T-S+1;
  long long lef(0), rig(INF64);
  while (rig-lef > 1)
  {
    long long mid((lef+rig)>>1);
    if (MaxFlow(mid) < FullFlow)
      lef = mid;
    else
      rig = mid;
  }
  if (rig == INF64 || MaxFlow(rig) < FullFlow)
    printf("-1");
  else
    printf("%lld", rig);
}

PKU2699：枚举答案+满流判定

注意到Strong Kings必然是最后连续的k个。枚举Strong Kings为最后的k个，那么：

每个选手i连边(i, T, score[i])
每场比赛k连边(S, k, 1)
对于选手i和j (i < j)，它们的比赛节点为k，连边(i, k, 1)。如果i不是Strong Kings或者score[i] >= score[j]那么连边(j, k, 1)，表示i和j同时都有可能赢这场比赛；否则不连，表示i必胜。

两两比赛，一共有n(n-1)/2场，如果满流（也就是n(n-1)/2），那么这种方案是可行的，继续向前推。

#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstring>
#include <string>
using std::cin;
using std::cout;

const int VERTEXS(10*10+12);
struct Edge
{
  int v, f;
  Edge *Next, *op;
} g[VERTEXS*VERTEXS];
int n, k, S(VERTEXS-2), T(VERTEXS-1), Nodes, TestData, MaxFlow, LinkSize, a[10], Dist[VERTEXS], DistCounter[VERTEXS];
Edge* Header[VERTEXS];
Edge* AddEdge(const int x, const int y, const int f, Edge* const op = NULL)
{
  Edge* node = g+(LinkSize++);
  node->v = y;
  node->f = f;
  node->op = op;
  node->Next = Header[x];
  Header[x] = node;
  if (op != NULL)
    op->op = node;
  return node;
}
int SAP(const int u, const int Delta)
{
  if (u == T)
    return Delta;
  int sum = 0, MinDist = Nodes;
  for (Edge* e = Header[u]; e; e = e->Next)
  {
    if (Dist[u]-1 == Dist[e->v] && e->f)
    {
      int d = SAP(e->v, std::min(Delta-sum, e->f));
      sum += d;
      e->f -= d;
      e->op->f += d;
      if (sum == Delta || Dist[S] >= Nodes)
        return Delta;
    }
    if (e->f)
      MinDist = std::min(MinDist, Dist[e->v]);
  }
  if (!sum)
    if (!--DistCounter[Dist[u]])
      Dist[S] = Nodes;
    else
      ++DistCounter[Dist[u] = MinDist+1];
  return sum;
}
int main()
{
  cin >> TestData;
  for (std::string s; TestData; --TestData)
  {
    while (std::getline(cin, s) && s.empty());
    std::stringstream ss(s);
    n = 0;
    while (ss)
      ss >> std::skipws >> a[n++];
    --n;
    int FullFlow(n*(n-1)/2);
    int k = n-1;
    for (; k >= 0; --k)
    {
      memset(Header, 0, sizeof(Header));
      memset(Dist, 0, sizeof(Dist));
      memset(DistCounter, 0, sizeof(DistCounter));
      LinkSize = 0;

      for (int i = 0; i != n; ++i)
        AddEdge(i, S, 0, AddEdge(S, i, a[i]));
      Nodes = n+2;
      for (int i = 0; i != n; ++i)
        for (int j = i+1; j < n; ++j, ++Nodes)
        {
          AddEdge(T, Nodes, 0, AddEdge(Nodes, T, 1));
          AddEdge(Nodes, i, 0, AddEdge(i, Nodes, 1));
          if (i < k || a[i] >= a[j])
            AddEdge(Nodes, j, 0, AddEdge(j, Nodes, 1));
        }

      int MaxFlow = 0;
      DistCounter[0] = Nodes;
      while (Dist[S] < Nodes)
        MaxFlow += SAP(S, 0x7FFFFFFF);
      if (MaxFlow != FullFlow)
        break;
    }
    cout << n-k-1 << std::endl;
  }
}

PKU3281：拆点+限流

对于每种食物food和饮料drink，连边(S, food, 1)，(drink, T, 1)，表示每种食品和饮料都只有一份。将牛i拆成i和i’两点，如果牛i愿意吃food，那么连边(food, i, ∞)，同理连边(i’, drink, ∞)。连边(i, i’, 1)表示一头牛只能吃一种食物和一种饮料。

最后的最大流就是有多少牛能够同时吃食物和喝饮料。

#include <iostream>
using std::cin;
using std::cout;

const int VERTEXS(2+100*2+100*2), S(VERTEXS-2), T(VERTEXS-1);
const int INF(0x3FFFFFFF);
struct Edge
{
  int v, f;
  Edge *Next, *op;
} g[VERTEXS*VERTEXS];
int LinkSize, MaxFlow, Nodes, n, F, D, Dist[VERTEXS], DistCounter[VERTEXS];
Edge* Header[VERTEXS];
Edge* AddEdge(const int x, const int y, const int f, Edge* const op = NULL)
{
  Edge* node = g+(LinkSize++);
  node->v = y;
  node->f = f;
  node->op = op;
  node->Next = Header[x];
  Header[x] = node;
  if (op != NULL)
    op->op = node;
  return node;
}
int SAP(const int u, const int Delta)
{
  if (u == T)
    return Delta;
  int sum = 0, MinDist = Nodes;
  for (Edge* e = Header[u]; e; e = e->Next)
  {
    if (Dist[u]-1 == Dist[e->v] && e->f)
    {
      int d = SAP(e->v, std::min(Delta-sum, e->f));
      sum += d;
      e->f -= d;
      e->op->f += d;
      if (sum == Delta || Dist[S] >= Nodes)
        return sum;
    }
    if (e->f)
      MinDist = std::min(MinDist, Dist[e->v]);
  }
  if (!sum)
    if (!--DistCounter[Dist[u]])
      Dist[S] = Nodes;
    else
      ++DistCounter[Dist[u] = MinDist+1];
  return sum;
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin >> n >> F >> D;
  for (int i = 0; i != F; ++i)
    AddEdge(i, S, 0, AddEdge(S, i, 1));
  for (int i = 0; i != D; ++i)
    AddEdge(T, F+i, 0, AddEdge(F+i, T, 1));
  for (int i = 0, f, d; i != n; ++i)
  {
    cin >> f >> d;
    for (int j = 0, x; j != f; ++j)
    {
      cin >> x;
      --x;
      AddEdge(F+D+i, x, 0, AddEdge(x, F+D+i, INF));
    }
    for (int j = 0, x; j != d; ++j)
    {
      cin >> x;
      --x;
      AddEdge(F+x, F+D+n+i, 0, AddEdge(F+D+n+i, F+x, INF));
    }
    AddEdge(F+D+n+i, F+D+i, 0, AddEdge(F+D+i, F+D+n+i, 1));
  }
  DistCounter[0] = Nodes = F+D+n*2+2;
  while (Dist[S] < Nodes)
    MaxFlow += SAP(S, INF);
  cout << MaxFlow;
}

QuarterGeek

Lequn Chen (abcdabcd987) 's Blog