图论

强联通分量（缩点）

int len_e, len_b, dfn[N], low[N], last[N], stk[N];
bool vis[N];
struct Edge {
  int y, n;
} edge[M];

void add_edge(int x, int y) {
  edge[++len_e] = (Edge){y, last[x]};
  last[x] = len_e;
}

void init() {
  len_e = 0;
  memset(last, 0, sizeof last);
}

void dfs(int x) {
  static int cnt = 0, top = 0;
  dfn[x] = low[x] = ++cnt;
  vis[x] = true;
  stk[++top] = x;
  for (int i = last[x]; i; i = edge[i].n) {
    int y = edge[i].y;
    if (!dfn[y]) {
      dfs(y);
      low[x] = min(low[x], low[y]);
    } else if (vis[y])
      low[x] = min(low[x], dfn[y]);
  }
  if (dfn[x] == low[x]) {
    ++len_b;
    int tmp;
    do {
      tmp = stk[top--];
      blk[tmp] = len_b;
      vis[tmp] = false;
    } while (x != tmp);
  }
}

void tarjan(int n) {
  len_b = 0;
  memset(dfn, 0, sizeof dfn);
  memset(vis, false, sizeof vis);
  for (int i = 1; i <= n; ++i)
    if (!dfn[i]) dfs(i);
}

强连通分量（割点）

int len_e;
int dfn[N], low[N], last[N];
bool cut[N];
struct Edge {
  int y, n;
} edge[M];

void add_edge(int x, int y) {
  edge[++len_e] = (Edge){y, last[x]};
  last[x] = len_e;
  edge[++len_e] = (Edge){x, last[y]};
  last[y] = len_e;
}

void init() {
  len_e = 0;
  memset(last, 0, sizeof last);
}

void dfs(int x, int fa) {
  static int cnt = 0;
  dfn[x] = low[x] = ++cnt;
  int child = 0;
  for (int i = last[x]; i; i = edge[i].n) {
    int y = edge[i].y;
    if (!dfn[y]) {
      dfs(y, fa);
      low[x] = min(low[x], low[y]);
      if (low[y] >= dfn[x] && x != fa) cut[x] = true;
      if (x == fa) ++child;
    }
    low[x] = min(low[x], dfn[y]);
  }
  if (child >= 2 && x == fa) cut[x] = true;
}

void tarjan(int n) {
  memset(dfn, 0, sizeof dfn);
  memset(cut, false, sizeof cut);
  for (int i = 1; i <= n; ++i)
    if (!dfn[i]) dfs(i, i);
}

差分约束系统

前置需求：负环

形如xi - xj <= c调add_cstr1()，形如xi - xj >= c调add_cstr2()

void add_cstr1(int i, int j, int c) { add_edge(j, i, c); }

void add_cstr2(int i, int j, int c) { add_edge(i, j, -c); }

bool diff_cstr(int n) {
  for (int i = 1; i <= n; ++i) add_edge(0, i, 0);
  return !spfa(n + 1, 0);
}

欧拉路径（有向图）

int len_ans;
int ans[M], in_deg[N], out_deg[N];
vector<int>::iterator cur[N];
vector<int> v[N];

void add_edge(int x, int y) {
  v[x].push_back(y);
  ++out_deg[x];
  ++in_deg[y];
}

void init() {
  memset(in_deg, 0, sizeof in_deg);
  memset(out_deg, 0, sizeof out_deg);
}

void dfs(int now) {
  for (auto &i = cur[now]; i != v[now].end();) {
    ++i;
    dfs(*(i - 1));
  }
  ans[len_ans++] = now;
}

bool Euler(int n, int m) {
  int cnt_in = 0, cnt_out = 0, tmp = 1;
  bool flag = true;
  for (int i = 1; i <= n && flag; ++i) {
    if (in_deg[i] + 1 == out_deg[i]) {
      ++cnt_in;
      tmp = i;
      if (cnt_in > 1) flag = false;
    } else if (in_deg[i] == out_deg[i] + 1) {
      ++cnt_out;
      if (cnt_out > 1) flag = false;
    } else if (in_deg[i] != out_deg[i])
      flag = false;
  }
  if (!flag) return false;
  len_ans = 0;
  for (int i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end());
  for (int i = 1; i <= n; ++i) cur[i] = v[i].begin();
  dfs(tmp);
  if (len_ans != m + 1) return false;
  reverse(ans, ans + len_ans);
  return true;
}

欧拉路径（无向图）

struct Edge {
  bool used;
  int y;
  Edge *inv;
} edge[M];
int len_ans, len_e;
int ans[M], deg[N];
vector<Edge *>::iterator cur[N];
vector<Edge *> v[N];

bool cmp(Edge *a, Edge *b) { return a->y < b->y; }

void add_edge(int x, int y) {
  ++len_e;
  edge[len_e] = (Edge){false, y, &edge[len_e] + 1};
  v[x].push_back(&edge[len_e]);
  ++len_e;
  edge[len_e] = (Edge){false, x, &edge[len_e] - 1};
  v[y].push_back(&edge[len_e]);
  ++deg[x];
  ++deg[y];
}

void init() {
  len_e = 0;
  memset(deg, 0, sizeof deg);
}

void dfs(int now) {
  for (auto &i = cur[now]; i != v[now].end();) {
    if ((*i)->used) {
      ++i;
      continue;
    }
    (*i)->used = true;
    (*i)->inv->used = true;
    ++i;
    dfs((*(i - 1))->y);
  }
  ans[len_ans++] = now;
}

bool Euler(int n, int m) {
  int cnt = 0, tmp = 1;
  bool flag = true;
  for (int i = 1; i <= n && flag; ++i)
    if (deg[i] & 1) {
      ++cnt;
      if (cnt == 1)
        tmp = i;
      else if (cnt > 2)
        flag = false;
    }
  if (!cnt)
    for (int i = 1; i <= n; ++i)
      if (deg[i]) {
        tmp = i;
        break;
      }
  if (!flag || cnt == 1) return false;
  len_ans = 0;
  for (int i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end(), cmp);
  for (int i = 1; i <= n; ++i) cur[i] = v[i].begin();
  dfs(tmp);
  if (len_ans != m + 1) return false;
  reverse(ans, ans + len_ans);
  return true;
}

SPFA

int len_e, dis[N], last[N], que[N];
bool vis[N];
struct Edge {
  int y, c, n;
} edge[M];

void add_edge(int x, int y, int c) {
  edge[++len_e] = (Edge){y, c, last[x]};
  last[x] = len_e;
}

void init() {
  len_e = 0;
  memset(last, 0, sizeof last);
}

int spfa(int s, int t) {
  memset(vis, false, sizeof vis);
  memset(dis, Inf, sizeof dis);
  int que_h = 0, que_t = 1;
  que[0] = s;
  dis[s] = 0;
  vis[s] = true;
  while (que_h != que_t) {
    int x = que[que_h++];
    if (que_h == N) que_h = 0;
    vis[x] = false;
    for (int i = last[x]; i; i = edge[i].n) {
      int y = edge[i].y, c = edge[i].c;
      if (dis[y] > dis[x] + c) {
        dis[y] = dis[x] + c;
        if (!vis[y]) {
          vis[y] = true;
          que[que_t++] = y;
          if (que_t == N) que_t = 0;
        }
      }
    }
  }
  return dis[t] == Inf ? -1 : dis[t];
}

SPFA（堆优化）

#define T 262144

int len_e, bit, dis[N], last[N];
struct Edge {
  int y, c, n;
} edge[M];

struct Tree {
  int id, data;
  friend bool operator==(const Tree &a, const Tree &b) {
    return a.id == b.id && a.data == b.data;
  }
} tree[T];

void add_edge(int x, int y, int c) {
  edge[++len_e] = (Edge){y, c, last[x]};
  last[x] = len_e;
}

void init() {
  len_e = 0;
  memset(last, 0, sizeof last);
}

inline Tree min(Tree a, Tree b) { return a.data < b.data ? a : b; }

void build(int n) {
  for (bit = 1; bit <= n; bit <<= 1)
    ;
  for (int i = bit; i < bit << 1; ++i) tree[i] = (Tree){i - bit, Inf};
  for (int i = bit - 1; i; --i) tree[i] = tree[i << 1];
}

const Tree &get() { return tree[1]; }

void modify(int id, int data) {
  id += bit;
  tree[id].data = data;
  for (id >>= 1; id; id >>= 1) {
    Tree tmp = min(tree[id << 1], tree[id << 1 | 1]);
    if (tmp == tree[id]) break;
    tree[id] = tmp;
  }
}

int dijk(int n, int s, int t) {
  build(n);
  memset(dis, Inf, sizeof dis);
  dis[s] = 0;
  modify(s, 0);
  for (Tree tmp = get(); tmp.data != Inf; tmp = get()) {
    int x = tmp.id;
    modify(x, Inf);
    for (int i = last[x]; i; i = edge[i].n) {
      int y = edge[i].y, c = edge[i].c;
      if (dis[y] > dis[x] + c) {
        dis[y] = dis[x] + c;
        modify(y, dis[y]);
      }
    }
  }
  return dis[t] == Inf ? -1 : dis[t];
}

负环

int len_e, dis[N], last[N], que[N], cnt[N];
bool vis[N];
struct Edge {
  int y, c, n;
} edge[M];

void add_edge(int x, int y, int c) {
  edge[++len_e] = (Edge){y, c, last[x]};
  last[x] = len_e;
}

void init() {
  len_e = 0;
  memset(last, 0, sizeof last);
}

bool spfa(int n, int s) {
  memset(vis, false, sizeof vis);
  memset(dis, Inf, sizeof dis);
  int que_h = 0, que_t = 1;
  que[0] = s, dis[s] = 0, cnt[s] = 0, vis[s] = true;
  while (que_h != que_t) {
    int x = que[que_h++];
    if (que_h == N) que_h = 0;
    vis[x] = false;
    for (int i = last[x]; i; i = edge[i].n) {
      int y = edge[i].y, c = edge[i].c;
      if (dis[y] > dis[x] + c) {
        dis[y] = dis[x] + c;
        if (!vis[y]) {
          vis[y] = true;
          cnt[y] = cnt[x] + 1;
          if (cnt[y] >= n) return true;
          que[que_t++] = y;
          if (que_t == N) que_t = 0;
        }
      }
    }
  }
  return false;
}

最大流（dinic）

int len_e, last[N], dis[N], que[N], cur[N];
struct Edge {
  int y, n;
  LL w;
} edge[M];

void add_edge(int x, int y, LL w) {
  edge[++len_e] = (Edge){y, last[x], w};
  last[x] = len_e;
  edge[++len_e] = (Edge){x, last[y], 0};
  last[y] = len_e;
}

void init() {
  len_e = -1;
  memset(last, -1, sizeof last);
}

bool bfs(int s, int t) {
  int que_h = 0, que_t = 1;
  que[0] = s;
  memset(dis, 0, sizeof dis);
  dis[s] = 1;
  while (que_h != que_t) {
    int x = que[que_h++];
    for (int i = last[x]; i != -1; i = edge[i].n) {
      int y = edge[i].y;
      if (!dis[y] && edge[i].w) {
        dis[y] = dis[x] + 1;
        que[que_t++] = y;
      }
    }
  }
  return dis[t];
}

LL dfs(int x, LL w_now, int t) {
  if (x == t) return w_now;
  for (int &i = cur[x]; i != -1; i = edge[i].n) {
    int y = edge[i].y;
    LL w = edge[i].w;
    if ((dis[y] == dis[x] + 1) && w) {
      LL ret = dfs(y, min(w, w_now), t);
      if (ret) {
        edge[i].w -= ret;
        edge[i ^ 1].w += ret;
        return ret;
      }
    }
  }
  return 0;
}

LL dinic(int s, int t) {
  LL ans = 0;
  while (bfs(s, t)) {
    memcpy(cur, last, sizeof last);
    for (LL x = dfs(s, Inf, t); x; x = dfs(s, Inf, t)) ans += x;
  }
  return ans;
}

预流推进

template <class T = int>
struct HLPP {
  const T INF = numeric_limits<T>::max();
  struct edge {
    int to, rev;
    T f;
  };
  int maxn, s{}, t{};
  edge edges[2 * M];
  int first_edge[N + 1]{};
  int _cur_edge[N]{};
  int nxt[N]{};
  int lst[N]{};
  T excess[N];
  int arc[N]{};
  int gapNxt[2 * N]{}, gapPrv[2 * N]{};
  int height[N]{};
  int highest{}, highestGap{}, work{};
  int q[2 * M]{};
  vector<int> degs;

  HLPP(vector<int> degrees, int s, int t) {
    this->s = s;
    this->t = t;
    maxn = degrees.size();
    assert(maxn <= N);
    int cnt = 0;
    for (int i = 0; i < maxn; ++i) {
      first_edge[i] = cnt;
      cnt += degrees[i];
    }
    first_edge[maxn] = cnt;
    copy(first_edge, first_edge + maxn + 1, _cur_edge);
    degs.swap(degrees);
  }

  void addEdge(int from, int to, int f, bool isDirected = true) {
    edges[_cur_edge[from]++] = {to, _cur_edge[to], f};
    edges[_cur_edge[to]++] = {from, _cur_edge[from] - 1, isDirected ? 0 : f};
  }

  void pushLst(int h, int v) {
    nxt[v] = lst[h];
    lst[h] = v;
  }

  void updHeight(int v, int nh) {
    if (height[v] != maxn) {
      gapNxt[gapPrv[v]] = gapNxt[v];
      gapPrv[gapNxt[v]] = gapPrv[v];
    }
    height[v] = nh;
    if (nh == maxn) return;
    highestGap = max(highestGap, nh);
    if (excess[v] > 0) {
      highest = max(highest, nh);
      pushLst(nh, v);
    }
    nh += maxn;
    gapNxt[v] = gapNxt[nh];
    gapPrv[v] = nh;
    gapNxt[nh] = v;
    gapPrv[gapNxt[v]] = v;
  }

  void globalRelabel() {
    work = 0;
    fill(height, height + maxn, maxn);
    fill(lst, lst + maxn, -1);
    iota(gapNxt, gapNxt + maxn, 0);
    iota(gapPrv, gapPrv + maxn, 0);
    height[t] = 0;
    q[0] = t;
    int sz = 1;
    for (size_t i = 0; i < sz; ++i) {
      int v = q[i];
      for (int ie = first_edge[v]; ie < first_edge[v + 1]; ++ie) {
        auto &e = edges[ie];
        if (height[e.to] == maxn && edges[e.rev].f > 0)
          q[sz++] = e.to, updHeight(e.to, height[v] + 1);
      }
      highest = highestGap = height[v];
    }
  }

  void push(int v, edge &e) {
    T df = min(excess[v], e.f);
    if (df > 0) {
      if (excess[e.to] == 0) pushLst(height[e.to], e.to);
      e.f -= df, edges[e.rev].f += df;
      excess[v] -= df, excess[e.to] += df;
    }
  }

  void discharge(int v) {
    int nh = maxn;
    for (int i = arc[v]; i < first_edge[v + 1]; i++) {
      auto &e = edges[i];
      if (e.f > 0) {
        if (height[v] == height[e.to] + 1) {
          push(v, e);
          if (excess[v] <= 0) {
            arc[v] = i;
            return;
          }
        } else
          nh = min(nh, height[e.to] + 1);
      }
    }
    for (int i = first_edge[v]; i < arc[v]; i++) {
      auto &e = edges[i];
      if (e.f > 0) {
        if (height[v] == height[e.to] + 1) {
          push(v, e);
          if (excess[v] <= 0) {
            arc[v] = i;
            return;
          }
        } else
          nh = min(nh, height[e.to] + 1);
      }
    }
    work++;
    if (gapNxt[gapNxt[height[v] + maxn]] != height[v] + maxn)
      updHeight(v, nh);
    else {
      int oldH = height[v];
      for (int h = oldH; h < highestGap + 1; h++) {
        for (int i = gapNxt[h + maxn]; i < maxn; i = gapNxt[i])
          height[i] = maxn;
        gapNxt[h + maxn] = gapPrv[h + maxn] = h + maxn;
      }
      highestGap = oldH - 1;
    }
  }

  T calc() {
    for (int v = 0; v < maxn; ++v) {
      sort(edges + first_edge[v], edges + first_edge[v + 1],
           [](edge &l, edge &r) { return l.to < r.to; });
      for (int i = first_edge[v]; i < first_edge[v + 1]; i++) {
        auto &e = edges[i];
        edges[e.rev].rev = i;
      }
    }
    copy(first_edge, first_edge + maxn, arc);
    fill(excess, excess + maxn, 0);
    excess[s] = INF, excess[t] = -INF;
    globalRelabel();
    for (int ie = first_edge[s]; ie < first_edge[s + 1]; ie++)
      push(s, edges[ie]);
    for (; highest >= 0; highest--)
      while (lst[highest] != -1) {
        int v = lst[highest];
        lst[highest] = nxt[v];
        if (height[v] == highest) {
          discharge(v);
          if (work > 4 * maxn) globalRelabel();
        }
      }
    return excess[t] + INF;
  }
};

vector<int> A1, A2, A3;

int solve(int nn, int mm, int s, int t) {
  s--;
  t--;
  vector<array<int, 3>> v(mm);
  vector<int> degs(nn);
  int i = 0;
  for (auto &x : v) {
    x[0] = A1[i] - 1;
    x[1] = A2[i] - 1;
    x[2] = A3[i++];
    ++degs[x[0]];
    ++degs[x[1]];
  }
  HLPP<> hlpp(degs, s, t);
  for (auto &x : v) hlpp.addEdge(x[0], x[1], x[2]);
  return hlpp.calc();
}

调用，A1是边的起点，A2是边的终点，A3是边的当前剩余流量。

for (int i = 1; i <= m * 2; ++i) {
  A1.push_back(b[i].from);
  A2.push_back(b[i].to);
  A3.push_back(b[i].last);
}
int maxflow = solve(n, m * 2, now.id, n);

最小费用最大流

int len_e, last[N], dis[N], que[N], pre[N], vis[N];
struct Edge {
  int y, n, w, c;
} edge[M];

void add_edge(int x, int y, int w, int c) {
  edge[++len_e] = (Edge){y, last[x], w, c};
  last[x] = len_e;
  edge[++len_e] = (Edge){x, last[y], 0, -c};
  last[y] = len_e;
}

void init() {
  len_e = -1;
  memset(last, -1, sizeof last);
}

bool spfa(int s, int t) {
  memset(dis, Inf, sizeof dis);
  memset(vis, false, sizeof vis);
  int que_h = 0, que_t = 1;
  dis[s] = 0, que[0] = s, vis[s] = true;
  while (que_h != que_t) {
    int x = que[que_h++];
    if (que_h == N) que_h = 0;
    vis[x] = false;
    for (int i = last[x]; i != -1; i = edge[i].n) {
      int y = edge[i].y;
      if (edge[i].w && dis[y] > dis[x] + edge[i].c) {
        dis[y] = dis[x] + edge[i].c;
        pre[y] = i;
        if (!vis[y]) {
          vis[y] = true;
          que[que_t++] = y;
          if (que_t == N) que_t = 0;
        }
      }
    }
  }
  return dis[t] != Inf;
}

void mcf(int s, int t, int &w_now, int &c_now) {
  w_now = c_now = 0;
  memset(pre, -1, sizeof pre);
  while (spfa(s, t)) {
    int x = Inf;
    for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].y]) x = min(x, edge[i].w);
    w_now += x;
    for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].y]) {
      c_now += edge[i].c * x;
      edge[i].w -= x;
      edge[i ^ 1].w += x;
    }
  }
}

最小费用最大流（堆优化）

#define T 16384

int len_e, bit, dis[N], last[N], pre[N];
struct Edge {
  int y, n, w, c;
} edge[M];

struct Tree {
  int id, data;
  friend bool operator==(const Tree &a, const Tree &b) {
    return a.id == b.id && a.data == b.data;
  }
} tree[T];

void add_edge(int x, int y, int w, int c) {
  edge[++len_e] = (Edge){y, last[x], w, c};
  last[x] = len_e;
  edge[++len_e] = (Edge){x, last[y], 0, -c};
  last[y] = len_e;
}

void init() {
  len_e = -1;
  memset(last, -1, sizeof last);
}

inline Tree min(Tree a, Tree b) { return a.data < b.data ? a : b; }

void build(int n) {
  for (bit = 1; bit <= n; bit <<= 1)
    ;
  for (int i = bit; i < bit << 1; ++i) tree[i] = (Tree){i - bit, Inf};
  for (int i = bit - 1; i; --i) tree[i] = tree[i << 1];
}

const Tree &get() { return tree[1]; }

void modify(int id, int data) {
  id += bit;
  tree[id].data = data;
  for (id >>= 1; id; id >>= 1) {
    Tree tmp = min(tree[id << 1], tree[id << 1 | 1]);
    if (tmp == tree[id]) break;
    tree[id] = tmp;
  }
}

bool dijk(int s, int t, int n) {
  build(n);
  memset(dis, Inf, sizeof dis);
  dis[s] = 0;
  modify(s, 0);
  for (Tree tmp = get(); tmp.data != Inf; tmp = get()) {
    int x = tmp.id;
    modify(x, Inf);
    for (int i = last[x]; i != -1; i = edge[i].n) {
      int y = edge[i].y;
      if (edge[i].w && dis[y] > dis[x] + edge[i].c) {
        dis[y] = dis[x] + edge[i].c;
        pre[y] = i;
        modify(y, dis[y]);
      }
    }
  }
  return dis[t] != Inf;
}

void mcf(int s, int t, int &w_now, int &c_now, int n) {
  w_now = c_now = 0;
  memset(pre, -1, sizeof pre);
  while (dijk(s, t, n)) {
    int x = Inf;
    for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].y]) x = min(x, edge[i].w);
    w_now += x;
    for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].y]) {
      c_now += edge[i].c * x;
      edge[i].w -= x;
      edge[i ^ 1].w += x;
    }
  }
}

最小生成树（Kruskal）

int father[N];

struct Edge {
  int x, y, w;
  friend bool operator<(const Edge &a, const Edge &b) { return a.w < b.w; }
} edge[M];

int get_father(int x) {
  return x == father[x] ? x : father[x] = get_father(father[x]);
}

int kruskal(int n, int m) {
  for (int i = 1; i <= n; ++i) father[i] = i;
  sort(edge + 1, edge + m + 1);
  int cnt = 0, ans = 0;
  for (int i = 1; i <= m; ++i) {
    int father_x = get_father(edge[i].x), father_y = get_father(edge[i].y);
    if (father_x != father_y) {
      father[father_x] = father_y;
      ++cnt;
      ans += edge[i].w;
    }
  }
  return cnt == n - 1 ? ans : -1;  //若图不连通，返回-1
}

最小生成树（Prim）

复杂度$ O(e + v \log v)$

#define T 16384

int len_e, bit, last[N];
bool vis[N];
struct Edge {
  int y, n, w;
} edge[M];

struct Tree {
  int id, data;
  friend bool operator==(const Tree &a, const Tree &b) {
    return a.id == b.id && a.data == b.data;
  }
} tree[T];

inline Tree min(Tree a, Tree b) { return a.data < b.data ? a : b; }

void build(int n) {
  for (bit = 1; bit <= n; bit <<= 1)
    ;
  for (int i = bit; i < bit << 1; ++i) tree[i] = (Tree){i - bit, Inf};
  for (int i = bit - 1; i; --i) tree[i] = tree[i << 1];
}

const Tree &get() { return tree[1]; }

void modify(int id, int data) {
  id += bit;
  tree[id].data = data;
  for (id >>= 1; id; id >>= 1) {
    Tree tmp = min(tree[id << 1], tree[id << 1 | 1]);
    if (tmp == tree[id]) break;
    tree[id] = tmp;
  }
}

void add_edge(int x, int y, int w) {
  edge[++len_e] = (Edge){y, last[x], w};
  last[x] = len_e;
  edge[++len_e] = (Edge){x, last[y], w};
  last[y] = len_e;
}

void init() {
  len_e = 0;
  memset(last, 0, sizeof last);
}

int prim(int n) {
  memset(vis, false, sizeof vis);
  build(n);
  int cnt = 0, ans = 0;
  modify(1, 0);
  for (Tree tmp = get(); tmp.data != Inf; tmp = get()) {
    int x = tmp.id, y = tmp.data;
    modify(x, Inf);
    vis[x] = true;
    ++cnt;
    ans += y;
    for (int i = last[x]; i; i = edge[i].n) {
      y = edge[i].y;
      if (!vis[y] && tree[y + bit].data > edge[i].w) modify(y, edge[i].w);
    }
  }
  return cnt == n ? ans : -1;  //若图不连通，返回-1
}

最小生成树（Borůvka）

复杂度$O(e \log v)$

int father[N], best[N];
bool used[M];
struct Edge {
  int x, y, w;
} edge[M];

int get_father(int x) {
  return x == father[x] ? x : father[x] = get_father(father[x]);
}

int boruvka(int n, int m) {
  for (int i = 1; i <= n; ++i) father[i] = i;
  memset(used, false, sizeof used);
  int cnt = 0, ans = 0;
  for (bool updated = true; updated;) {
    updated = false;
    memset(best, 0, sizeof best);
    for (int i = 1; i <= m; ++i)
      if (!used[i]) {
        int father_x = get_father(edge[i].x), father_y = get_father(edge[i].y);
        if (father_x != father_y) {
          if (!best[father_x] || edge[i].w < edge[best[father_x]].w)
            best[father_x] = i;
          if (!best[father_y] || edge[i].w < edge[best[father_y]].w)
            best[father_y] = i;
        }
      }
    for (int i = 1; i <= n; ++i) {
      if (best[i] && !used[best[i]]) {
        updated = true;
        used[best[i]] = true;
        father[get_father(edge[best[i]].x)] = get_father(edge[best[i]].y);
        ++cnt;
        ans += edge[best[i]].w;
      }
    }
  }
  return cnt == n - 1 ? ans : -1;  //若图不连通，返回-1
}

带花树（一般图最大匹配）

int len_e = 0, last[N];
struct Edge {
  int y, n;
} edge[M];

void add_edge(int x, int y) {
  edge[++len_e] = (Edge){y, last[x]};
  last[x] = len_e;
  edge[++len_e] = (Edge){x, last[y]};
  last[y] = len_e;
}

int f[N], tim, dic[N], pre[N], match[N], tp[N], que[N];
int hed = 1, tal = 0, n, m, a, b;

int findfa(int x) { return x == f[x] ? x : f[x] = findfa(f[x]); }

int lca(int x, int y) {
  ++tim;
  while (true) {
    if (x) {
      x = findfa(x);
      if (dic[x] == tim)
        return x;
      else
        dic[x] = tim, x = pre[match[x]];
    }
    swap(x, y);
  }
}

void shrink(int x, int y, int p) {
  while (findfa(x) != p) {
    pre[x] = y, y = match[x];
    if (tp[y] == 2) tp[y] = 1, que[++tal] = y;
    if (findfa(x) == x) f[x] = p;
    if (findfa(y) == y) f[y] = p;
    x = pre[y];
  }
}

bool AUG(int x) {
  for (int i = 1; i <= n; i++) f[i] = i;
  memset(tp, 0, sizeof(tp));
  memset(pre, 0, sizeof(pre));
  hed = 1, tal = 0;
  que[++tal] = x;
  tp[x] = 1;
  while (hed <= tal) {
    int tmp = que[hed++];
    for (int i = last[tmp]; i; i = edge[i].n) {
      int nmp = edge[i].y;
      if (findfa(tmp) == findfa(nmp) || tp[nmp] == 2) continue;
      if (!tp[nmp]) {
        tp[nmp] = 2, pre[nmp] = tmp;
        if (!match[nmp]) {
          int now = nmp, la, mtmp;
          while (now) {
            mtmp = pre[now];
            la = match[mtmp];
            match[now] = mtmp;
            match[mtmp] = now;
            now = la;
          }
          return true;
        }
        tp[match[nmp]] = 1;
        que[++tal] = match[nmp];
      } else if (tp[nmp] == 1) {
        int l = lca(tmp, nmp);
        shrink(tmp, nmp, l);
        shrink(nmp, tmp, l);
      }
    }
  }
  return false;
}

int work() {
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += (!match[i] && AUG(i));
  return ans;
}

Matrix-Tree 定理

对于已经得出的基尔霍夫矩阵，去掉其随意一行一列得出的矩阵的行列式，其绝对值为生成树的个数

for (int i = 1; i <= m; i++) {
  cin >> a >> b;
  graph[a][a]++, graph[b][b]++;
  graph[a][b] = graph[b][a] = -1;
}

Cayley公式

一个含有n个节点的完全图的生成树的个数为 $n^{n-2}$，即带有标号的n个节点的无根树的个数为$n^{n-2}$

LGV引理

LGV 引理仅适用于有向无环图

$\omega(P)$ 表示 $P$ 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 $1$）（事实上，边权可以为生成函数）

$e(u, v)$ 表示 $u$ 到 $v$ 的每一条路径 $P$ 的 $\omega(P)$ 之和，即 $e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)$。

起点集合 $A$，是有向无环图点集的一个子集，大小为 $n$。

终点集合 $B$，也是有向无环图点集的一个子集，大小也为 $n$。

一组 $A\rightarrow B$ 的不相交路径 $S$：$S_i$ 是一条从 $Ai$ 到 $B{\sigma(S)_i}$ 的路径（$\sigma(S)$ 是一个排列），对于任何 $i\ne j$，$S_i$ 和 $S_j$ 没有公共顶点。

$N(\sigma)$ 表示排列 $\sigma$ 的逆序对个数。

$$ M = \begin{bmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\ \vdots&\vdots&\ddots&\vdots\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)\end{bmatrix} $$

$$ \det(M)=\sum\limits{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits{i=1}^n \omega(S_i) $$

其中 $\sum\limits_{S:A\rightarrow B}$ 表示满足上文要求的 $A\rightarrow B$ 的每一组不相交路径 $S$。