Dinic（最大流/最小割+费用流）

最大流/最小割：

 1 typedef long long ll;
 2 const int N = 1e4 + 5;
 3 const int M = 2e5 + 5;
 4 const ll inf = 1e18;
 5 int n, m, s, t, tot;
 6 ll head[N], to[M], nxt[M], val[M], d[N];
 7 inline void link(int u, int v, ll w) // link
 8 {
 9     to[tot] = v;
10     nxt[tot] = head[u];
11     val[tot] = w;
12     head[u] = tot++;
13 }
14 inline void add(int u, int v, ll w) // 加边
15 {
16     link(u, v, w);
17     link(v, u, 0);
18 }
19 queue<int> q;
20 inline bool bfs() // 分层
21 {
22     q = queue<int>();
23     memset(d, 0, sizeof(d));
24     d[s] = 1;
25     q.emplace(s);
26     while (!q.empty())
27     {
28         int tmp = q.front();
29         q.pop();
30         for (int i = head[tmp]; ~i; i = nxt[i])
31             if (!d[to[i]] && val[i])
32             {
33                 d[to[i]] = d[tmp] + 1;
34                 q.emplace(to[i]);
35                 if (to[i] == t)
36                     return true;
37             }
38     }
39     return false;
40 }
41 inline ll dfs(ll x, ll flow) // 求解
42 {
43     if (x == t)
44         return flow;
45     ll rest = flow;
46     for (int i = head[x]; ~i; i = nxt[i])
47         if (d[to[i]] == d[x] + 1 && val[i])
48         {
49             ll t = dfs(to[i], min(rest, val[i]));
50             if (!t)
51                 d[to[i]] = 0;
52             rest -= t;
53             val[i] -= t;
54             val[i ^ 1] += t;
55         }
56     return flow - rest;
57 }
58 inline ll Dinic()
59 {
60     ll res = 0;
61     while (bfs())
62         res += dfs(s, inf);
63     return res;
64 }

费用流：

 1 typedef long long ll;
 2 const int N = 5e3 + 5;
 3 const int M = 5e4 + 5;
 4 const ll inf = 0x3f3f3f3f3f3f3f3f;
 5 int n, m, s, t, tot;
 6 ll head[N], to[M << 1], nxt[M << 1], val[M << 1], c[M << 1], d[N], flw, cst;
 7 bool vis[N];
 8 inline void link(int u, int v, ll w, ll cost)
 9 {
10     to[tot] = v;
11     nxt[tot] = head[u];
12     val[tot] = w;
13     c[tot] = cost;
14     head[u] = tot++;
15 }
16 inline void add(int u, int v, ll w, ll cost)
17 {
18     link(u, v, w, cost);
19     link(v, u, 0, -cost);
20 }
21 queue<int> q;
22 inline bool spfa()
23 {
24     memset(d, 0x3f, sizeof(d));
25     q.emplace(s);
26     d[s] = 0;
27     vis[s] = true;
28     while (!q.empty())
29     {
30         int tmp = q.front();
31         q.pop();
32         vis[tmp] = false;
33         for (int i = head[tmp]; ~i; i = nxt[i])
34             if (val[i] && d[to[i]] > d[tmp] + c[i])
35             {
36                 d[to[i]] = d[tmp] + c[i];
37                 if (!vis[to[i]])
38                 {
39                     vis[to[i]] = true;
40                     q.emplace(to[i]);
41                 }
42             }
43     }
44     return d[t] != inf;
45 }
46 inline ll dfs(ll x, ll flow)
47 {
48     if (x == t)
49         return flow;
50     vis[x] = true;
51     ll rest = flow;
52     for (int i = head[x]; ~i; i = nxt[i])
53         if (!vis[to[i]] && val[i] && d[to[i]] == d[x] + c[i])
54         {
55             ll t = dfs(to[i], min(rest, val[i]));
56             if (!t)
57                 d[to[i]] = 0;
58             rest -= t;
59             val[i] -= t;
60             val[i ^ 1] += t;
61             cst += t * c[i];
62         }
63     vis[x] = false;
64     return flow - rest;
65 }
66 inline void MCMF()
67 {
68     while (spfa())
69         flw += dfs(s, inf);
70     cout << flw << ' ' << cst;
71 }