最大流/最小割:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 }View Code
费用流:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 }View Code
标签:tmp,费用,return,val,int,ll,最小,rest,Dinic From: https://www.cnblogs.com/creation-hy/p/Dinic.html