二分图

二分图最大匹配

图的匹配，即由一组没有公共端点的不是圈的边构成的集合，我们这里需要使得这个集合尽可能大，即寻找二分图的最大匹配

这里需要先了解两个定义：

• 交错路：给定图G的一个匹配M，如果一条路径的边交替出现在M中和不出现在M中，我们称之为一条M-交错路径
• 增广路（增广轨）：如果一条M-交错路径，它的两个端点都不与M中的边关联，我们称这条路径叫做M-增广路径

匈牙利算法

该算法本质上就是不停地找增广路并更新答案，复杂度为$O(nm)$。

算法的正确性证明可以看这里

struct augment_path {
  vector<vector<int> > g;
  vector<int> pa;  // 匹配
  vector<int> pb;
  vector<int> vis;  // 访问
  int n, m;         // 两个点集中的顶点数量
  int dfn;          // 时间戳记
  int res;          // 匹配数

  augment_path(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    vis = vector<int>(n);
    g.resize(n);
    res = 0;
    dfn = 0;
  }

  void add(int from, int to) {
    assert(0 <= from && from < n && 0 <= to && to < m);
    g[from].push_back(to);
  }

  bool dfs(int u) {
    vis[u] = dfn;
    for (int v : g[u]) {
      if (pb[v] == -1) {
        pb[v] = u;
        pa[u] = v;
        return true;
      }
    }
    for (int v : g[u]) {
      if (vis[pb[v]] != dfn && dfs(pb[v])) {
        pb[v] = u;
		pa[u] = v;
        return true;
      }
    }
    return false;
  }

  int solve() {
    while (true) {
      dfn++;
      int cnt = 0;
      for (int i = 0; i < n; i++) {
        if (pa[i] == -1 && dfs(i)) {
          cnt++;
        }
      }
      if (cnt == 0) {
        break;
      }
      res += cnt;
    }
    return res;
  }
};

最大流

将二分图最大匹配转换成网络流模型。将源点连上左边所有点，右边所有点连上汇点，容量皆为 1。原来的每条边从左往右连边，容量也皆为 1，最大流即最大匹配。如果使用 Dinic 算法求解这个模型，时间复杂度可以来到较为优秀的$O(\sqrt{n}m)$

复杂度分析：

这个网络中，所有边的流量均为 1，且除了源点和汇点外的所有点，都满足入边最多只有一条，或出边最多只有一条。我们称这样的网络为单位网络。对于单位网络，一轮增广的时间复杂度为 $O(m)$，因为每条边只会被考虑最多一次。
接下来我们试着求出增广轮数的上界。假设我们已经先完成了前$\sqrt{n}$轮增广，因为汇点的层数在每次增广后均严格增加，因此所有长度不超过$\sqrt{n}$的增广路都已经在之前的增广过程中被增广。设前$\sqrt{n}$轮增广后，网络的流量为$f$，而整个网络的最大流为$f'$，设两者间的差值为$d=f'-f$。
因为网络上所有边的流量均为 1，所以我们还需要找到$d$条增广路才能找到网络最大流。又因为单位网络的特点，这些增广路不会在源点和汇点以外的点相交。因此这些增广路至少经过了$d\sqrt{n}$ 个点（每条增广路的长度至少为 $\sqrt{n}$），且不能超过$n$个点。因此残量网络上最多还存在$\sqrt{n}$条增广路。也即最多还需增广$\sqrt{n}$轮。
综上，对于包含二分图最大匹配在内的单位网络，Dinic 算法可以在$O(\sqrt{n}m)$的时间内求出其最大流。

#define maxn 250
#define INF 0x3f3f3f3f

struct Edge {
  int from, to, cap, flow;
  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct Dinic {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  int d[maxn], cur[maxn];
  bool vis[maxn];

  void init(int n) {
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }

  int DFS(int x, int a) {
    if (x == t || a == 0) return a;
    int flow = 0, f;
    for (int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i] ^ 1].flow -= f;
        flow += f;
        a -= f;
        if (a == 0) break;
      }
    }
    return flow;
  }

  int Maxflow(int s, int t) {
    this->s = s;
    this->t = t;
    int flow = 0;
    while (BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, INF);
    }
    return flow;
  }
};

例题

P1640 [SCOI2010]连续攻击游戏

每件装备只能用一次，如果把攻击序列建成点，就是装备和攻击顺序的匹配。比如属性值是3和5，那么这件装备要么在3位置要么在5位置被使用。按攻击顺序开始匹配，一旦匹配不成功，根据题意就必须中止。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 1010000
#define MAXM 4040000
#define X(n) (n+10000)
struct Edge
{
    int to,nex;
    Edge(){}
    Edge(int _to, int _nex):to(_to),nex(_nex){}
};
Edge e[MAXM+5];
int first[MAXN+5], book[MAXN+5], match[MAXN+5], N, tot, id, op;
void Add(int a, int b)
{
    e[tot] = Edge(b,first[a]);
    first[a] = tot++;
    return;
}
bool DFS(int x)
{
    for(register int u = first[x], v; u+1; u = e[u].nex)
        if(book[v=e[u].to]-id)
        {
            book[v] = id;
            if(!match[v] || DFS(match[v]))
            {
                match[x] = v, match[v] = x;
                return true;
            }
        }
    return false;
}
int Hungary()
{
    int ans = 0;
    for(register int i = id = 1; i <= 10000; i++, id++)
        if(DFS(i))
            ans++;
        else
            break;
    return ans;
}
int main()
{
    scanf("%d",&N), memset(first,-1,sizeof(first));
    for(register int i = 1, j; i <= N; i++)
        for(j = 0; j < 2; j++)
            scanf("%d",&op), Add(op,X(i)), Add(X(i),op);
    printf("%d\n",Hungary());
     return 0;
}