前言：

$ $

$\quad\quad$ 本文章主要谈论二分图 & 网络流有关内容，算是一次自我整理吧…

$\quad\quad$ 以下内容参(ban)考(yun)于xht37的博客，和部分二分图 & 网络流资料。

$ $

正文：

$\quad\quad$ 二分图：可化为两关联点集 $A , B$，且 $A , B$ 各自内部无连边的图。

$\quad\quad$ 二分图性质：二分图内无奇环，无奇环的图是二分图。

$\quad\quad$ 二分图判定： $O(n)$ 染色即可。

$ $

• 例题：51nod 2911 部落冲突。

• 解析：没啥好说的，裸题一道。

• 代码：

  #include <bits/stdc++.h>

  using namespace std;

  inline int read();

  const int N = 1e6 + 10;

  int n, m;

  vector <int > link[N];

  int col[N], flag;

  void dfs(int wz, int color)
  {
      if(flag) return ;

      col[wz] = color;

      for(int k = 0; k < (int )link[wz].size(); k++)
      {
          int to = link[wz][k];
          if(col[wz] == col[to])
              flag = 1;
          if(flag) return ;

          if(!col[to])
              dfs(to, color ^ 1);
      }
  }

  int main()
  {
      while(scanf("%d %d", &n, &m) != EOF)
      {
          flag = 0;
          memset(col, 0, sizeof(col));
          for(register int k = 1; k <= m; k++)
          {
              int u = read(), v = read();
              link[u].push_back(v);
              link[v].push_back(u);
          }

          dfs(1, 2);

          if(!flag) puts("Yes");
          else puts("No");
          memset(link, 0, sizeof(link));
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 匹配：在图论中，一个匹配是任意两条边都没有公共定点的边的集合。

$\quad\quad$ 匹配边：对于一个匹配，属于该匹配中的边是匹配边，不属于该匹配中的边是非匹配边。

$\quad\quad$ 匹配点：对于一个匹配，与匹配边有关的点是匹配点，无关的点是非匹配点。

$\quad\quad$ 最大匹配：一个图的所有匹配中，包含匹配边数量最多的匹配。

$\quad\quad$ 例如：

$\quad\quad$ 上图中，$\{1-2,3-5\}$ 是一组匹配，匹配边是 $1-2$ 和 $3-5$，其余的边是非匹配边，匹配点是 $1,2,3,5$，非匹配点是 $4$，最大匹配为：$\{1-2,3-5\}$（不唯一）。

$\quad\quad$ 一般图最大匹配可以用带花树解决，但相当不常见，这里不介绍了、

$ $

$\quad\quad$ 二分图最大匹配（重点）：一个无向图图的所有匹配中，包含匹配边数量最多的匹配。

$\quad\quad$ 算法比较多，这里只提最普适的最大流算法：拆点，每个点分为入点和出点，出入点之间连 $1$，把二分图分为左右两部分，左部分入点流 $1$ 连 $S$，右部分出点流 $1$ 连 $E$，把两部分点之间的连边换成左出点连右入点，跑 Dinic。

$\quad\quad$ 实践发现：因为二分图最大匹配中没有额外限制，且某些流具有等价性，所以该图可以不拆点，上述方法等价于：把二分图分为左右两部分，左点流 $1$ 连 $S$，右点流 $1$ 连 $E$，左右点之间按题目所给的连边，直接跑 Dinic。

$ $

• 例题：洛谷 P3386 【模板】二分图最大匹配

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1010;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, e, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  signed main()
  {
      n = read(), m = read(), e = read(), S = n + m + 1, E = S + 1;
      for(register int k = 1; k <= n; k++)
          add_edge(S, k, 1);
      for(register int k = n + 1; k <= n + m; k++)
          add_edge(k, E, 1);

      for(register int k = 1; k <= e; k++)
      {
          int u = read(), v = read() + n;
          add_edge(u, v, 1);
      }

      Dinic();

      printf("%d", max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 二分图最大匹配的要点：模型中的元素可以分为两部分，且所有相关关系集中于这两部分之间，各部分内部元素之间无相关关系。

$ $

• 例题：洛谷 U64970 車的放置

• 解析：找内部没有联系的元素：行，列。我们把行，列看做二分图的两边，如果某一个点可以放下棋子，就在对应行，列之间连边流 $1$，再让起点到每一行，每一列到终点流 $1$ 即可。

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 410;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, t, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  bool place[210][210];

  signed main()
  {
      n = read(), m = read(), t = read(), S = n + m + 1, E = S + 1;
      for(register int k = 1; k <= t; k++)
      {
          int x = read(), y = read();
          place[x][y] = 1;
      }

      for(register int k = 1; k <= n; k++)
          for(int i = 1; i <= m; i++)
              if(!place[k][i])
                  add_edge(k, i + n, 1);
      for(register int k = 1; k <= n; k++)
          add_edge(S, k, 1);
      for(register int k = 1; k <= m; k++)
          add_edge(k + n, E, 1);

      Dinic();

      printf("%d", max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 完备匹配：所有点都是匹配点的匹配，匹配边数与点数相等。

$\quad\quad$ 多重匹配：在一个点可以被包含在多条边中的条件下进行的匹配。

$\quad\quad$ 解决方案：在二分图上的话，最大流改改就行。

$\quad\quad$ 带权最大匹配：每一条边有一个权值，求一个匹配使得其中所有边的权值和最大（最大匹配即为所有边权值为 $1$ 的带权最大匹配）。

$\quad\quad$ 解决方案：在二分图上的话，把最大流换成费用流就行。

$\quad\quad$ 但是注意到：我们跑费用流求出来匹配一定是一个最大匹配，而带权最大匹配不一定是一个最大匹配，所以直接费用流不能保证跑出带权最大匹配。

$\quad\quad$ 为了解决这个问题，可以新建一个节点，向 $S$ 流 $+\inf$，费用 $0$，向右边所有点流 $1$，费用 $0$,这样一来，我们带权最大匹配就一定是一个最大匹配了。

$ $

$\quad\quad$ 残量网络：对于一种二分图最大匹配，若边 $(x,y)$ 未流满，则连接 $x,y$，构成的网络。

$\quad\quad$ 可行边与必须边（见过，不很常用，不放例题）：

• $\quad$ 可行边：在某些二分图最大匹配的方案中被选上的边。

• $\quad$ 必须边：在所有二分图最大匹配的方案中都要选的边。

$\quad\quad$ 求法同样分两种情况讨论：

• $\quad$ 最大匹配是完备匹配：

$\quad\quad\quad$ 把二分图中的非匹配边看作从左部向右部的有向边，匹配边看作从右部向左部的有向边，构成一张新的有向图。

$\quad\quad\quad$ 必须边 ：$(x,y)$ 是当前二分图的匹配边，且 $x,y$ 在新的有向图中属于不同的强连通分量。

$\quad\quad\quad$ 可行边 ：$(x,y)$ 是当前二分图的匹配边，或 $x,y$ 在新的有向图中属于同一个强连通分量。

• $\quad$ 最大匹配不一定是完备匹配（普适）：

$\quad\quad\quad$ 必须边 ：$(x,y)$ 的流量为 $1$，且 $x,y$ 在残量网络上属于不同的强连通分量。

$\quad\quad\quad$ 可行边 ：$(x,y)$ 的流量为 $1$，或 $x,y$ 在残量网络上属于同一个强连通分量。

$ $

$ $

$\quad\quad$ 最小点覆盖：在一张图中，所有边至少有一个顶点在一个点集 T中，这样的点集 T 的最少元素个数。

$\quad\quad$ 定理：二分图最小点覆盖等于二分图最大匹配。

$\quad\quad$ 解法：对着二分图，直接跑最大匹配即可。

$\quad\quad$ 要点：二者中必须选一个（一条边连两个点），选了之后另一些元素就不用选了（一个点连着多条边）。

$ $

• 例题：UVA1194 Machine Schedule

• 解析：明确要点，一个任务，要么在这台机器上执行，要么在另一台机器上执行，一台机器开到某个模式后可以执行这个模式下的所有任务，所以把 $A$ 机器的所有模式看做二分图的一边， $B$ 机器的所有模式看做另一边，如果一个任务用 $A_i/B_j$ 模式，就把 $A_i$ 到 $B_j$ 连边，跑最小点覆盖即可，注意：机器一开始就是 $0$ 模式。

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 210;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, K, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  void init()
  {
      max_flow = 0, tot = 1;
      S = n + m + 1, E = S + 1;
      memset(link, 0, sizeof(link));
  }

  signed main()
  {
      while(scanf("%d", &n) != EOF && n)
      {
          scanf("%d %d", &m, &K), init();
          for(register int k = 1; k <= K; k++)
          {
              read();
              int u = read() + 1, v = read() + 1;
              add_edge(u, v + n, 1);
          }
          for(register int k = 2; k <= n; k++)
              add_edge(S, k, 1);
          for(register int k = n + 2; k <= n + m; k++)
              add_edge(k, E, 1);
          Dinic();

          printf("%d\n", max_flow);
      }


      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 最小边覆盖：在一张图中，选中一些边，组成 $E$ 集合，使得图中所有点被包含在 $E$ 内，这样的 $E$ 集合内的最少元素个数。

$\quad\quad$ 定理：二分图最小边覆盖等于节点数减最大匹配。

$\quad\quad$ 与最小点覆盖一体两面，用得不多。

$ $

$\quad\quad$ 最大独立集：在一张图中，选出一个点集 $V$，使得集合内的点两两间没有边相连，这样的 $V$ 集合内的最多元素个数。

$\quad\quad$ 定理：二分图最大独立集等于节点数减最大匹配。

$\quad\quad$ 解法：还是对着二分图跑最大匹配。

$\quad\quad$ 要点：某些元素互斥，利用互斥关系连边，最后跑出的最大独立集就是互斥元素的最大数。

$ $

• 例题： 洛谷 P3355 骑士共存问题

• 解析： 找要点,各个棋子之间是互斥的，所以套用最大独立集的模型，把能一步到达的位置之间互相连边，最后求出的最大独立集就是答案。从马的走法可以看出，它回到一个点需要 $2/4/6…$ 步，均是偶环，所以该图是二分图，可以利用奇偶关系/染色法把图分成两部分，跑 Dinic 即可。

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 4e4 + 10;
  const int M = 5e6 + 10;

  inline int read();

  int n, m, K, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  bool pla[210][210];

  int py[8][2] = {2, 1, -2, 1, 2, -1, -2, -1, 1, -2, 1, 2, -1, 2, -1, -2};

  signed main()
  {
      n = read(), m = read(), S = n * n + 1, E = S + 1;
      for(register int k = 1; k <= m; k++)
      {
          int x = read(), y = read();
          pla[x][y] = 1;
      }

      for(register int k = 1; k <= n; k++)
          for(int i = 1; i <= n; i++)
              if(!pla[k][i])
              {
                  if((k + i) % 2)
                      add_edge(S, (k - 1)*n + i, 1);
                  else
                      add_edge((k - 1)*n + i, E, 1);
              }

      for(register int k = 1; k <= n; k++)
          for(int i = 1; i <= n; i++)
              if(!pla[k][i] && (k + i) % 2)
                  for(int j = 0; j < 8; j++)
                  {
                      int x = k + py[j][0], y = i + py[j][1];
                      if(x > n || x < 1 || y > n || y < 1) continue;
                      if(!pla[x][y]) add_edge((k - 1)*n + i, (x - 1)*n + y, 1);
                  }

      Dinic(), printf("%d", n * n - m - max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$ $

$\quad\quad$ 最大团：在一张图中，选出一个点集 $V$，使得集合内的点两两间都有边相连，这样的 $V$ 集合内的最多元素个数。

$\quad\quad$ 定理：无向图（不一定是二分图）的最大团等于其补图的最大独立集。

$\quad\quad$ 解法：求补图，再求最大独立集。

$\quad\quad$ 要点：一般图的最大团是 NPC 的，看到最大团就知道该去找补图了。

$ $

$ $

$\quad\quad$ DAG 最小路径点覆盖：在 DAG 中，用最少的不相交的链覆盖整个 DAG 上的点，问链的最少条数。

$\quad\quad$ 解法：拆点，把一个点拆成$A,B$两个点，按DAG上连边，把每一个$A$点连向其他$B$点，得到二分图，跑最大匹配，最小路径数等于（原）点数减二分图最大匹配数。

$\quad\quad$ 要点：用不交的路径覆盖 DAG。

$ $

• 例题：洛谷P2764 最小路径覆盖问题

• 解析：本题难点在于输出路径，应该是有复杂度比较优秀的算法的，不过因为网络流自身复杂度比较大，暴力并查集即可。

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1010;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  int fa[N];

  int find(int x)
  {
      return fa[x] == x ? x : fa[x] = find(fa[x]);
  }

  signed main()
  {
      n = read(), m = read(), S = n * 2 + 1, E = S + 1;
      for(register int k = 1; k <= n; k++) fa[k] = k;
      for(register int k = 1; k <= n; k++) add_edge(S, k, 1);
      for(register int k = 1; k <= n; k++) add_edge(k + n, E, 1);

      for(register int k = 1; k <= m; k++)
      {
          int u = read(), v = read();
          add_edge(u, v + n, 1);
      }
      Dinic();

      for(register int k = 1; k <= n; k++)
      {
          for(int i = 0; i < (int )link[k].size(); i++)
          {
              int num = link[k][i], to = edge[num].to;
              if(!edge[num].flow && to - n >= 1 && to - n <= n) fa[find(to - n)] = find(k);
          }
      }

      for(register int k = 1; k <= n; k++)
          if(find(k))
          {
              for(int i = 1; i <= n; i++)
                  if(find(i) == fa[k])
                      printf("%d ", i);
              printf("\n");
              fa[fa[k]] = 0;
          }

      printf("%d", n - max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 二分图主要内容差不多就上面那些，以最大匹配为中心，通过最小覆盖，最大独立集/团，路径覆盖 等分支向外延伸，模型很隐蔽，与其它算法结合后，难度相当大。

$\quad\quad$ 下面是网络流的一些知识，网络流个人感觉比较随心所欲，各种建边方法层出不穷，难题要 AC 几乎只能靠感觉，所以下面只提几个比较经典的网络流概念和模型。

$ $

$ $

$\quad\quad$ 网络流：一种特殊的有向图，每条边 $(x,y)$ 有一权值 $c(x,y)$ 表示该边容量，图中（一般）有两特殊点 $S,T$ ，$S$ 是源点， $T$ 是汇点。（这个字母表示和我常用的有差异）

$\quad\quad$ 定义函数 $f(x,y)$ 表示 $x$ 到 $y$ 的实际流量。

$\quad\quad$ 定理：$f(x,y)\le c(x,y)$，$\sum f(u,x)=\sum f(x,v)$，

$\quad\quad$ 即：一条边的实际流量小于该边容量，流入一个点的流等于从这个点流出的流。

$\quad\quad$ 还有一个完善系统的定理： $f(u,v)$ 等价于 $-f(v,u)$（可类比负数）。

$\quad\quad$ 我们称 $\sum f(x,E)$ 为该网络流量。

$\quad\quad$ 当然，我们理解网络流都不是按照上面的定义来的，我们是按照自来水系统来的。

$ $

$\quad\quad$ 最大流/费用流：不写，自己百度去。

$\quad\quad$ 割：割去后使得源汇点之间不连通的边集。

$\quad\quad$ 最小割（重点）：流量最小的一组割。

$\quad\quad$ 定理：最小割等于最大流。

$\quad\quad$ 基础模型：删点/删边 模型

$\quad\quad$ 即对于一张网络，如何删点/边使其不连通。

$\quad\quad$ 删边好说，直接跑最小割就行。删点的话就要看情况处理了。

$ $

• 例题：UVA1660 电视网络 Cable TV Network

• 题意：求最少删除多少个点，使图不连通（未给出源汇点）。

• 解析： 显然，对于删点，我们是没办法直接处理的，考虑把一个点的删除转化成一条边上的删除。这种转化常用的方法就是拆点：把一个点拆成出入两个点，之间流 1。注意：可以删的（点转化出的边）流需要的值，不能删的（原边）流无穷大值。

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1010;
  const int M = 5e5 + 10;

  inline int read();

  int n, m, tot = 1, max_flow, S, E;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int f)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = f;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  int deep[N], cur[N];
  queue <int > q;

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      deep[S] = 0, q.push(S);

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(deep[to] > deep[wz] + 1 && edge[num].flow)
              {
                  deep[to] = deep[wz] + 1;
                  q.push(to);
              }
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = cur[wz]; k < (int )link[wz].size(); cur[wz] = k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;
          if(deep[to] == deep[wz] + 1 && edge[num].flow && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;

          if(used == flow)
              break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  int ls[M], ans;

  signed main()
  {
      while(scanf("%d %d", &n, &m) != EOF)
      {
          tot = 1, ans = n;
          memset(link, 0, sizeof(link));

          for(register int k = 1; k <= n; k++)
              add_edge(k, k + n, 1);

          for(register int k = 1; k <= m; k++)
          {
              int u = read() + 1, v = read() + 1;
              add_edge(u + n, v, 0x3f3f3f3f);
              add_edge(v + n, u, 0x3f3f3f3f);
          }

          for(register int k = 1; k <= tot; k++)
              ls[k] = edge[k].flow;

          for(register int k = 1; k <= n; k++)
              for(int i = k + 1; i <= n; i++)
              {
                  max_flow = 0;
                  for(int j = 1; j <= tot; j++)
                      edge[j].flow = ls[j];
                  S = k + n, E = i, Dinic();
                  ans = min(ans, max_flow);
              }

          printf("%d\n", ans);
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 进阶模型： 集合划分模型

$\quad\quad$ 即有多个元素，求把它们划分成两类的最优方案。

$\quad\quad$ 一种常见的题目是：给定每个元素划分成两类的不同代价，加上限制条件 $w(x,y)$ 表示 $x,y$ 不在同一个类别中需要额外付出的代价，求最小代价。

$\quad\quad$ 解决方式是：建 $S,E$ 代表两类，对每一个元素向 $S,E$ 连流为代价的边，限制 $w(x,y)$ 转化成 $x,y$ 两点间的流 $w$ 双向边，跑最小割即可。

$ $

• 例题：洛谷 P2057 [SHOI2007]善意的投票

• 解析：在确定本题可以最小割求解后，思路就很显然了。抓要点：把人分成睡觉和不睡觉两类，不妨把睡觉设为 $S$，不睡觉设为 $E$ ，对每个人，向意愿的一侧流 0（不连边），不愿的一侧流 1，好朋友之间流 1，跑最小割即可。

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  inline int read();

  const int N = 1e3;
  const int M = 1e6;

  int S, E, tot = 1, max_flow, n, m;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int c)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = c;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  queue <int > q;
  int deep[N], cur[N];

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      q.push(S), deep[S] = 0;

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(edge[num].flow && deep[to] > deep[wz] + 1)
                  deep[to] = deep[wz] + 1, q.push(to);
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = 0; k < (int )link[wz].size(); k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;

          if(edge[num].flow && deep[to] == deep[wz] + 1 && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;
          if(used == flow) break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  signed main()
  {
      n = read(), m = read(), S = n + 1, E = S + 1;
      for(register int k = 1; k <= n; k++)
      {
          int x = read();
          if(x == 0) add_edge(S, k, 1);
          else add_edge(k, E, 1);
      }

      for(register int k = 1; k <= m; k++)
      {
          int u = read(), v = read();
          add_edge(u, v, 1);
          add_edge(v, u, 1);
      }

      Dinic(), printf("%d\n", max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$ $

$\quad\quad$ 特殊模型：平面图最小割。

$\quad\quad$ 平面图：边与边只在定点相交的图（除顶点外无交点/交点都是顶点/平面被各条边分为互不相交的区域）。

$\quad\quad$ 平面图的对偶图：把平面图每一块区域当做点，若平面图中两块区域有交边就将其连边，得到的图是该平面图对偶图。

$\quad\quad$ 细节：连边的边权等于公共边的流量，把源点和汇点在不穿过其他边的前提下相连，得到的区域代表起点区域，剩下的区域代表终点区域。

$\quad\quad$ 定理：平面图最大流=平面图最小割=对偶图最短路。

$ $

• 例题：洛谷 P4001 [ICPC-Beijing 2006]狼抓兔子

• 解析：显然，以左上角点为源点，右下角点为汇点，我们要求的就是平面图最小割，直接转化成对偶图最短路即可。

• 代码（懒得优化，需要吸氧）：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  inline int read();

  const int N = 3e6;
  typedef pair <int , int > P;
  #define mp make_pair

  struct node
  {
      int to, len;
      node (int a, int b)
      {
          to = a, len = b;
      }
      node () { }
  };
  vector <node > link[N];

  void add_edge(int u, int v, int w)
  {
      link[u].push_back(node(v, w));
      link[v].push_back(node(u, w));
  }

  int n, m, S, E;

  int dis[N], sol[N];

  priority_queue <P, vector <P> , greater<P> > q;

  void dij()
  {
      memset(dis, 0x3f, sizeof(dis));
      q.push(mp(0, S)), dis[S] = 0;

      while(!q.empty())
      {
          int wz = q.top().second;
          q.pop();

          if(sol[wz]) continue;
          sol[wz] = 1;

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int to = link[wz][k].to, len = link[wz][k].len;
              if(dis[to] > dis[wz] + len)
              {
                  dis[to] = dis[wz] + len;
                  q.push(mp(dis[to], to));
              }
          }
      }

      printf("%d\n", dis[E]);
  }

  signed main()
  {
      n = read() - 1, m = read() - 1, S = n * m * 2 + 1, E = S + 1;
      for(register int k = 0; k <= n; k++)
          for(int i = 1; i <= m; i++)
          {
              if(k == 0) add_edge(i * 2, E, read());
              else if(k == n) add_edge((n - 1)*m * 2 + i * 2 - 1, S, read());
              else add_edge(k * m * 2 + i * 2, (k - 1)*m * 2 + i * 2 - 1, read());
          }
      for(register int k = 1; k <= n; k++)
          for(int i = 0; i <= m; i++)
          {
              if(i == 0) add_edge(S, (k - 1)*m * 2 + 1, read());
              else if(i == m) add_edge(E, k * m * 2, read());
              else add_edge((k - 1)*m * 2 + i * 2 + 1, (k - 1)*m * 2 + i * 2, read());
          }
      for(register int k = 1; k <= n; k++)
          for(register int i = 1; i <= m; i++)
              add_edge((k - 1)*m * 2 + i * 2, (k - 1)*m * 2 + i * 2 - 1, read());

      dij();

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 引申模型：最大权闭合子图：给定 $n$ 个元素，每个元素有一个价值 $v_i$ ，元素之间有限制关系 $w(x,y)$ 表示选了 $x$ 才能选 $y$，求最大价值。

$\quad\quad$ 解法：对于所有元素，若其权值为正，向源点流 $v_i$，否则向汇点流 $-v_i$，对于 $w(x,y)$，从 $x$ 流 $\inf$ 到 $y$，跑出最小割，答案为原正权和-最小割。

$\quad\quad$ 要点：先 XX 才能 XX，要求无选择个数限制（否则就尝试树形DP吧）。

$ $

• 例题：洛谷 P2762 太空飞行计划问题

• 解析：几乎是板子，最后要求输出方案，方案就是最后与 $S$ 连通的实验和仪器，证明略过，可以自行百度。

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <iostream>
  #include <algorithm>

  using namespace std;

  inline int read();

  const int N = 1e3;
  const int M = 1e6;

  int S, E, tot = 1, max_flow, n, m;

  struct node
  {
      int to, flow;
  } edge[M];
  vector <int > link[N];

  void add_edge(int u, int v, int c)
  {
      link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = c;
      link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0;
  }

  queue <int > q;
  int deep[N], cur[N];

  bool bfs()
  {
      memset(cur, 0, sizeof(cur));
      memset(deep, 0x3f, sizeof(deep));
      q.push(S), deep[S] = 0;

      while(!q.empty())
      {
          int wz = q.front();
          q.pop();

          for(int k = 0; k < (int )link[wz].size(); k++)
          {
              int num = link[wz][k], to = edge[num].to;
              if(edge[num].flow && deep[to] > deep[wz] + 1)
                  deep[to] = deep[wz] + 1, q.push(to);
          }
      }

      return deep[E] != 0x3f3f3f3f;
  }

  int dfs(int wz, int flow)
  {
      if(wz == E)
      {
          max_flow += flow;
          return flow;
      }

      int used = 0;

      for(int k = 0; k < (int )link[wz].size(); k++)
      {
          int num = link[wz][k], to = edge[num].to, Flow;

          if(edge[num].flow && deep[to] == deep[wz] + 1 && (Flow = dfs(to, min(flow - used, edge[num].flow))))
              edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, used += Flow;
          if(used == flow) break;
      }

      return used;
  }

  void Dinic()
  {
      while(bfs())
          dfs(S, 0x3f3f3f3f);
  }

  int answ;

  signed main()
  {
      m = read(), n = read(), S = m + n + 1, E = S + 1;
      for(register int k = 1; k <= m; k++)
      {
          int x = read();
          add_edge(S, k, x), answ += x;

          char tools[10000];
          memset(tools, 0, sizeof tools);
          cin.getline(tools, 10000);
          int ulen = 0, tool;
          while (sscanf(tools + ulen, "%d", &tool) == 1)
          {
              add_edge(k, tool + m, 0x3f3f3f3f);

              if (tool == 0)
                  ulen++;
              else
              {
                  while (tool)
                  {
                      tool /= 10;
                      ulen++;
                  }
              }
              ulen++;
          }
      }

      for(register int k = 1; k <= n; k++)
          add_edge(k + m, E, read());
      Dinic();

      for(register int k = 1; k <= m; k++)
          if(deep[k] != 0x3f3f3f3f)
              printf("%d ", k);
      puts("");

      for(register int k = m + 1; k <= m + n; k++)
          if(deep[k] != 0x3f3f3f3f)
              printf("%d ", k - m);
      puts("");

      printf("%d\n", answ - max_flow);

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$\quad\quad$ 好像还剩上下界网络流的知识点来着…懒得写了。

$\quad\quad$ 费用流基本上就没啥板子了，得对题下算法......

$\quad\quad$ 稍微放一道简单的例题吧。

$ $

• 例题： 洛谷 P2045 方格取数加强版

• 解析： 没啥难度，拆点后稍微连一下跑费用流就行了。

• 代码：

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

inline int read();

const int N = 1e4;
const int M = 5e6;

int S, E, tot = 1, max_flow, min_cost, n, m;

struct node
{
    int to, flow, cost;
} edge[M];
vector <int > link[N];

void add_edge(int u, int v, int c, int w)
{
    link[u].push_back(++tot), edge[tot].to = v, edge[tot].flow = c, edge[tot].cost = w;
    link[v].push_back(++tot), edge[tot].to = u, edge[tot].flow = 0, edge[tot].cost = -w;
}

queue <int > q;
int dis[N], in[N];

bool SPFA()
{
    memset(in, 0, sizeof(in));
    memset(dis, 0xef, sizeof(dis));
    q.push(S), dis[S] = 0;

    while(!q.empty())
    {
        int wz = q.front();
        q.pop(), in[wz] = 0;

        for(int k = 0; k < (int )link[wz].size(); k++)
        {
            int num = link[wz][k], to = edge[num].to, len = edge[num].cost;
            if(edge[num].flow && dis[to] < dis[wz] + len)
            {
                dis[to] = dis[wz] + len;
                if(!in[to]) in[to] = 1, q.push(to);
            }
        }
    }

    return dis[E] != 0xefefefef;
}

int dfs(int wz, int flow)
{
    if(wz == E)
    {
        max_flow += flow;
        return flow;
    }

    in[wz] = 1;
    int used = 0;

    for(int k = 0; k < (int )link[wz].size(); k++)
    {
        int num = link[wz][k], to = edge[num].to, len = edge[num].cost, Flow;

        if(!in[to] && edge[num].flow && dis[to] == dis[wz] + len && (Flow = dfs(to, min(flow - used, edge[num].flow))))
            edge[num].flow -= Flow, edge[num ^ 1].flow += Flow, min_cost += Flow * len, used += Flow;
        if(used == flow) break;
    }

    in[wz] = 0;
    return used;
}

void Dinic()
{
    while(SPFA())
        dfs(S, 0x3f3f3f3f);
}

int py[2][2] = {0, 1, 1, 0};

signed main()
{
    n = read(), m = read(), S = n * n * 2 + 1, E = S + 1;
    add_edge(S, 1, m, 0), add_edge(n * n * 2, E, m, 0);
    for(register int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
        {
            add_edge((k - 1)*n + i, (k - 1)*n + i + n * n, 0x3f3f3f3f, 0);
            add_edge((k - 1)*n + i, (k - 1)*n + i + n * n, 1, read());
        }

    for(register int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < 2; j++)
            {
                int x = k + py[j][0], y = i + py[j][1];
                if(x >= 1 && x <= n && y >= 1 && y <= n)
                    add_edge((k - 1)*n + i + n * n, (x - 1)*n + y, 0x3f3f3f3f, 0);
            }

    Dinic(), printf("%d\n", min_cost);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$ $

结语：

$\quad\quad$ 上下界可行流咕掉了。