图论算法模板整理
//无向图的双连通分量int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt; // 割顶的bccno无意义struct Edge { int u, v; };vector<int> G[maxn], bcc[maxn];stack<Edge> S;int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; Edge e = (Edge){u, v}; if(!pre[v]) { // 没有访问过v S.push(e); child++; int lowv = dfs(v, u); lowu = min(lowu, lowv); // 用后代的low函数更新自己 if(lowv >= pre[u]) { iscut[u] = true; bcc_cnt++; bcc[bcc_cnt].clear(); for(;;) { Edge x = S.top(); S.pop(); if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; } if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; } if(x.u == u && x.v == v) break; } } } else if(pre[v] < pre[u] && v != fa) { S.push(e); lowu = min(lowu, pre[v]); // 用反向边更新自己 } } if(fa < 0 && child == 1) iscut[u] = 0; return lowu;}void find_bcc(int n) { // 调用结束后S保证为空，所以不用清空 memset(pre, 0, sizeof(pre)); memset(iscut, 0, sizeof(iscut)); memset(bccno, 0, sizeof(bccno)); dfs_clock = bcc_cnt = 0; for(int i = 0; i < n; i++) if(!pre[i]) dfs(i, -1); };//无向图求桥 & 双连通分量int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(!pre[v]) { int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1; //标记所有桥 } else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]); } return low[u] = lowu; } void dfs1(int u) { bccno[u] = bcc_cnt; int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(!bccno[v] && edges[G[u][i]].flag != 1) dfs1(v);//不经过桥 } } void find_bcc() { CLR(pre, 0); CLR(bccno, 0); dfs_clock = bcc_cnt = 0; REP(i, n) if(!pre[i]) dfs(i, -1); REP(i, n) if(!bccno[i]) bcc_cnt++, dfs1(i); } //有向图的强连通分量vector<int> G[maxn];int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;stack<int> S;void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if(!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if(lowlink[u] == pre[u]) { scc_cnt++; for(;;) { int x = S.top(); S.pop(); sccno[x] = scc_cnt; if(x == u) break; } }}void find_scc(int n) { dfs_clock = scc_cnt = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for(int i = 0; i < n; i++) if(!pre[i]) dfs(i);};//无向图的欧拉回路 保存在G中void add(int u, int v){ g[u][v] = g[v][u] = 1; degree[u]++, degree[v]++; }void Euler() { FF(i, 1, n+1) if(degree[i]) { int u = i; while(true) { FF(j, 1, n+1) if(g[u][j] && g[j][u]) { g[j][u] = 0; degree[u]--, degree[i]--; u = j; break; } if(u == i) break; } } } //2-sat dfs版本struct TwoSAT { int n; vector<int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2], c; bool dfs(int x) { if (mark[x^1]) return false; if (mark[x]) return true; mark[x] = true; S[c++] = x; for (int i = 0; i < G[x].size(); i++) if (!dfs(G[x][i])) return false; return true; } void init(int n) { this->n = n; for (int i = 0; i < n*2; i++) G[i].clear(); memset(mark, 0, sizeof(mark)); } // x = xval or y = yval void add_clause(int x, int xval, int y, int yval) { x = x * 2 + xval; y = y * 2 + yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve() { for(int i = 0; i < n*2; i += 2) if(!mark[i] && !mark[i+1]) { c = 0; if(!dfs(i)) { while(c > 0) mark[S[--c]] = false; if(!dfs(i+1)) return false; } } return true; }};//堆优化的Dijkstrastruct Edge { int from, to, dist;};struct HeapNode { int d, u; bool operator < (const HeapNode& rhs) const { return d > rhs.d; }};struct Dijkstra { int n, m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; // 是否已永久标号 int d[maxn]; // s到各个点的距离 int p[maxn]; // 最短路中的上一条弧 void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int dist) { edges.push_back((Edge){from, to, dist}); m = edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { priority_queue<HeapNode> Q; for(int i = 0; i < n; i++) d[i] = INF; d[s] = 0; memset(done, 0, sizeof(done)); Q.push((HeapNode){0, s}); while(!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if(done[u]) continue; done[u] = true; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; Q.push((HeapNode){d[e.to], e.to}); } } } } // dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t） void GetShortestPaths(int s, int* dist, vector<int>* paths) { dijkstra(s); for(int i = 0; i < n; i++) { dist[i] = d[i]; paths[i].clear(); int t = i; paths[i].push_back(t); while(t != s) { paths[i].push_back(edges[p[t]].from); t = edges[p[t]].from; } reverse(paths[i].begin(), paths[i].end()); } }};//spfa判负环struct Edge { int from, to; double dist;};struct spfa { int n, m; vector<Edge> edges; vector<int> G[maxn]; bool inq[maxn]; // 是否在队列中 double d[maxn]; // s到各个点的距离 int p[maxn]; // 最短路中的上一条弧 int cnt[maxn]; // 进队次数 void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, double dist) { edges.push_back((Edge){from, to, dist}); m = edges.size(); G[from].push_back(m-1); } bool negativeCycle() { queue<int> Q; memset(inq, 0, sizeof(inq)); memset(cnt, 0, sizeof(cnt)); for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); } while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; } } } } return false; }};//kruskal求次小生成树 maxcost[i][j]为i->j的瓶颈路 //对于MST边u, v maxcost[u][v] = 0int n, m, x[maxn], y[maxn], p[maxn];int pa[maxn];int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; } //G保存MST C保存MST边权vector<int> G[maxn];vector<double> C[maxn];struct Edge { int x, y; double d; bool operator < (const Edge& rhs) const { return d < rhs.d; }};Edge e[maxn*maxn];double maxcost[maxn][maxn];vector<int> nodes;void dfs(int u, int fa, double facost) { for(int i = 0; i < nodes.size(); i++) { int x = nodes[i]; maxcost[u][x] = maxcost[x][u] = max(maxcost[x][fa], facost); } nodes.push_back(u); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(v != fa) dfs(v, u, C[u][i]); }}double MST() { sort(e, e+m); for(int i = 0; i < n; i++) { pa[i] = i; G[i].clear(); C[i].clear(); } int cnt = 0; double ans = 0; for(int i = 0; i < m; i++) { int x = e[i].x, y = e[i].y, u = findset(x), v = findset(y); double d = e[i].d; if(u != v) { pa[u] = v; G[x].push_back(y); C[x].push_back(d); G[y].push_back(x); C[y].push_back(d); ans += d; if(++cnt == n-1) break; } } return ans;}//prim求次小生成树//use[u][v] = 2时，边<u, v>在MST上//use[u][v] = 1时，原图存在边<u, v>。//f[u][v]表示u->v的最小瓶颈路 初始化为0double prim() { int pre[maxn] = {-1}; bool vis[maxn] = {0}; double d[maxn], ret = 0; FF(i, 1, n+1) d[i] = INF; d[1] = 0; FF(i, 1, n+1) { int pos; double tmp = INF; FF(j, 1, n+1) if(!vis[j] && d[j] < tmp) tmp = d[j], pos = j; if(pre[pos] != -1) { use[pre[pos]][pos] = use[pos][pre[pos]] = 2; FF(j, 1, n+1) if(vis[j]) f[pos][j] = f[j][pos] = max(f[j][pre[pos]], g[pre[pos]][pos]); } vis[pos] = 1; ret += d[pos]; FF(j, 1, n+1) if(!vis[j] && use[pos][j] && g[pos][j] < d[j]) d[j] = g[pos][j], pre[j] = pos; } return ret; }//LCAstruct LCA { int n; int fa[maxn]; // 父亲数组 int cost[maxn]; // 和父亲的费用 int L[maxn]; // 层次（根节点层次为0） int anc[maxn][logmaxn]; // anc[p][i]是结点p的第2^i级父亲。anc[i][0] = fa[i] int maxcost[maxn][logmaxn]; // maxcost[p][i]是i和anc[p][i]的路径上的最大费用 // 预处理，根据fa和cost数组求出anc和maxcost数组 void preprocess() { for(int i = 0; i < n; i++) { anc[i][0] = fa[i]; maxcost[i][0] = cost[i]; for(int j = 1; (1 << j) < n; j++) anc[i][j] = -1; } for(int j = 1; (1 << j) < n; j++) for(int i = 0; i < n; i++) if(anc[i][j-1] != -1) { int a = anc[i][j-1]; anc[i][j] = anc[a][j-1]; maxcost[i][j] = max(maxcost[i][j-1], maxcost[a][j-1]); } } // 求p到q的路径上的最大权 int query(int p, int q) { int tmp, log, i; if(L[p] < L[q]) swap(p, q); for(log = 1; (1 << log) <= L[p]; log++); log--; int ans = -INF; for(int i = log; i >= 0; i--) if (L[p] - (1 << i) >= L[q]) { ans = max(ans, maxcost[p][i]); p = anc[p][i];} if (p == q) return ans; // LCA为p for(int i = log; i >= 0; i--) if(anc[p][i] != -1 && anc[p][i] != anc[q][i]) { ans = max(ans, maxcost[p][i]); p = anc[p][i]; ans = max(ans, maxcost[q][i]); q = anc[q][i]; } ans = max(ans, cost[p]); ans = max(ans, cost[q]); return ans; // LCA为fa[p]（它也等于fa[q]） } };//固定根的最小树型图，邻接矩阵写法struct MDST { int n; int w[maxn][maxn]; // 边权 int vis[maxn]; // 访问标记，仅用来判断无解 int ans; // 计算答案 int removed[maxn]; // 每个点是否被删除 int cid[maxn]; // 所在圈编号 int pre[maxn]; // 最小入边的起点 int iw[maxn]; // 最小入边的权值 int max_cid; // 最大圈编号 void init(int n) { this->n = n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) w[i][j] = INF; } void AddEdge(int u, int v, int cost) { w[u][v] = min(w[u][v], cost); // 重边取权最小的 } // 从s出发能到达多少个结点 int dfs(int s) { vis[s] = 1; int ans = 1; for(int i = 0; i < n; i++) if(!vis[i] && w[s][i] < INF) ans += dfs(i); return ans; } // 从u出发沿着pre指针找圈 bool cycle(int u) { max_cid++; int v = u; while(cid[v] != max_cid) { cid[v] = max_cid; v = pre[v]; } return v == u; } // 计算u的最小入弧，入弧起点不得在圈c中 void update(int u) { iw[u] = INF; for(int i = 0; i < n; i++) if(!removed[i] && w[i][u] < iw[u]) { iw[u] = w[i][u]; pre[u] = i; } } // 根结点为s，如果失败则返回false bool solve(int s) { memset(vis, 0, sizeof(vis)); if(dfs(s) != n) return false; memset(removed, 0, sizeof(removed)); memset(cid, 0, sizeof(cid)); for(int u = 0; u < n; u++) update(u); pre[s] = s; iw[s] = 0; // 根结点特殊处理 ans = max_cid = 0; for(;;) { bool have_cycle = false; for(int u = 0; u < n; u++) if(u != s && !removed[u] && cycle(u)){ have_cycle = true; // 以下代码缩圈，圈上除了u之外的结点均删除 int v = u; do { if(v != u) removed[v] = 1; ans += iw[v]; // 对于圈外点i，把边i->v改成i->u（并调整权值）；v->i改为u->i // 注意圈上可能还有一个v'使得i->v'或者v'->i存在，因此只保留权值最小的i->u和u->i for(int i = 0; i < n; i++) if(cid[i] != cid[u] && !removed[i]) { if(w[i][v] < INF) w[i][u] = min(w[i][u], w[i][v]-iw[v]); w[u][i] = min(w[u][i], w[v][i]); if(pre[i] == v) pre[i] = u; } v = pre[v]; } while(v != u); update(u); break; } if(!have_cycle) break; } for(int i = 0; i < n; i++) if(!removed[i]) ans += iw[i]; return true; }};//KM int W[maxn][maxn], n;int Lx[maxn], Ly[maxn]; // 顶标int left[maxn]; // left[i]为右边第i个点的匹配点编号bool S[maxn], T[maxn]; // S[i]和T[i]为左/右第i个点是否已标记bool match(int i){ S[i] = true; for(int j = 1; j <= n; j++) if (Lx[i]+Ly[j] == W[i][j] && !T[j]){ T[j] = true; if (!left[j] || match(left[j])){ left[j] = i; return true; } } return false;}void update(){ int a = INF; for(int i = 1; i <= n; i++) if(S[i]) for(int j = 1; j <= n; j++) if(!T[j]) a = min(a, Lx[i]+Ly[j] - W[i][j]); for(int i = 1; i <= n; i++) { if(S[i]) Lx[i] -= a; if(T[i]) Ly[i] += a; }}void KM() { for(int i = 1; i <= n; i++) { left[i] = Lx[i] = Ly[i] = 0; for(int j = 1; j <= n; j++) Lx[i] = max(Lx[i], W[i][j]); } for(int i = 1; i <= n; i++) { for(;;) { for(int j = 1; j <= n; j++) S[j] = T[j] = false; if(match(i)) break; else update(); } }}// 二分图最大基数匹配，邻接矩阵写法 struct BPM { int n, m; // 左右顶点个数 int G[maxn][maxn]; // 邻接表 int left[maxn]; // left[i]为右边第i个点的匹配点编号，-1表示不存在 bool T[maxn]; // T[i]为右边第i个点是否已标记 void init(int n, int m) { this->n = n; this->m = m; memset(G, 0, sizeof(G)); } bool match(int u){ for(int v = 0; v < m; v++) if(G[u][v] && !T[v]) { T[v] = true; if (left[v] == -1 || match(left[v])){ left[v] = u; return true; } } return false; } // 求最大匹配 int solve() { memset(left, -1, sizeof(left)); int ans = 0; for(int u = 0; u < n; u++) { // 从左边结点u开始增广 memset(T, 0, sizeof(T)); if(match(u)) ans++; } return ans; }};// 二分图最大基数匹配求覆盖集struct BPM { int n, m; // 左右顶点个数 vector<int> G[maxn]; // 邻接表 int left[maxn]; // left[i]为右边第i个点的匹配点编号，-1表示不存在 bool T[maxn]; // T[i]为右边第i个点是否已标记 int right[maxn]; // 求最小覆盖用 bool S[maxn]; // 求最小覆盖用 void init(int n, int m) { this->n = n; this->m = m; for(int i = 0; i < n; i++) G[i].clear(); } void AddEdge(int u, int v) { G[u].push_back(v); } bool match(int u){ S[u] = true; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (!T[v]){ T[v] = true; if (left[v] == -1 || match(left[v])){ left[v] = u; right[u] = v; return true; } } } return false; } // 求最大匹配 int solve() { memset(left, -1, sizeof(left)); memset(right, -1, sizeof(right)); int ans = 0; for(int u = 0; u < n; u++) { // 从左边结点u开始增广 memset(S, 0, sizeof(S)); memset(T, 0, sizeof(T)); if(match(u)) ans++; } return ans; } // 求最小覆盖。X和Y为最小覆盖中的点集 int mincover(vector<int>& X, vector<int>& Y) { int ans = solve(); memset(S, 0, sizeof(S)); memset(T, 0, sizeof(T)); for(int u = 0; u < n; u++) if(right[u] == -1) match(u); // 从所有X未盖点出发增广 for(int u = 0; u < n; u++) if(!S[u]) X.push_back(u); // X中的未标记点 for(int v = 0; v < m; v++) if(T[v]) Y.push_back(v); // Y中的已标记点 return ans; } };//ISAPstruct Edge { int from, to, cap, flow; };bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct ISAP { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 int p[maxn]; // 可增广路上的上一条弧 int num[maxn]; // 距离标号计数 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(t); vis[t] = 1; d[t] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]^1]; if(!vis[e.from] && e.cap > e.flow) { vis[e.from] = 1; d[e.from] = d[x] + 1; Q.push(e.from); } } } return vis[s]; } void ClearAll(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void ClearFlow() { for(int i = 0; i < edges.size(); i++) edges[i].flow = 0; } int Augment() { int x = t, a = INF; while(x != s) { Edge& e = edges[p[x]]; a = min(a, e.cap-e.flow); x = edges[p[x]].from; } x = t; while(x != s) { edges[p[x]].flow += a; edges[p[x]^1].flow -= a; x = edges[p[x]].from; } return a; } int Maxflow(int s, int t, int need) { this->s = s; this->t = t; int flow = 0; BFS(); memset(num, 0, sizeof(num)); for(int i = 0; i < n; i++) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { flow += Augment(); if(flow >= need) return flow; x = s; } int ok = 0; for(int i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to] + 1) { // Advance ok = 1; p[e.to] = G[x][i]; cur[x] = i; // 注意 x = e.to; break; } } if(!ok) { // Retreat int m = n-1; // 初值注意 for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m+1]++; cur[x] = 0; // 注意 if(x != s) x = edges[p[x]].from; } } return flow; } vector<int> Mincut() { // call this after maxflow BFS(); vector<int> ans; for(int i = 0; i < edges.size(); i++) { Edge& e = edges[i]; if(!vis[e.from] && vis[e.to] && e.cap > 0) ans.push_back(i); } return ans; } void Reduce() { for(int i = 0; i < edges.size(); i++) edges[i].cap -= edges[i].flow; } void print() { printf("Graph:\n"); for(int i = 0; i < edges.size(); i++) printf("%d->%d, %d, %d\n", edges[i].from, edges[i].to , edges[i].cap, edges[i].flow); }};//Dinicstruct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); }struct Dinic { int n, m, s, t; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 void ClearAll(int n) { for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void ClearFlow() { for(int i = 0; i < edges.size(); i++) edges[i].flow = 0; } 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); vis[s] = 1; d[s] = 0; 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; } };//MCMFstruct Edge { int from, to, cap, flow, cost; };struct MCMF { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; // 是否在队列中 int d[maxn]; // Bellman-Ford int p[maxn]; // 上一条弧 int a[maxn]; // 可改进量 void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap, int cost) { edges.push_back((Edge){from, to, cap, 0, cost}); edges.push_back((Edge){to, from, 0, 0, -cost}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s, int t, LL& ans) { for(int i = 0; i < n; i++) d[i] = INF; memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(e.cap > e.flow && d[e.to] > d[u] + e.cost) { d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } } } } if(d[t] == INF) return false;//s-t不连通 失败退出 if(d[t] > 0) return false;//不固定流量的最小费用流 ans += (LL)d[t] * (LL)a[t]; int u = t; while(u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return true; } // 需要保证初始网络中没有负权圈 LL Mincost(int s, int t) { LL cost = 0; while(BellmanFord(s, t, cost)); return cost; } };