Thanks I_am_the_Lord_Voldemort.

Author: https://mirror.codeforces.com/profile/Libingyue20111

This is the English version of the article.

https://www.luogu.com.cn/article/kw6klidj

A few days ago, Libingyue2011 came across this problem.

Wow, two paths, and you can't collect the same point multiple times.

So the novice Libingyue2011 didn't want to write dynamic programming (DP) anymore, as he found it too difficult.

Then he learned from a blue-covered book that this problem could be solved using cost flow, and even the enhanced version could be solved along with it.

So he solved it.

Therefore, this is actually a detailed explanation of network flow.

Network Flow 1

Some Knowledge about Networks and Flows

A network is a directed graph where each edge has a weight $$$c$$$.

In a network, there are two special nodes called the source ($$$S$$$) and the sink ($$$T$$$).

$$$c(x,y)$$$ denotes the capacity of the edge $$$(x,y)$$$.

Define the function $$$f(x,y)$$$ as the flow function of the edge $$$(x,y)$$$.

It satisfies the following properties: 1. Capacity Constraint: $$$f(x,y) \lt c(x,y)$$$. 2. Skew Symmetry: $$$f(x,y) = -f(y,x)$$$. 3. Flow Conservation: For any node $$$x$$$ that is neither $$$S$$$ nor $$$T$$$,
$$$\sum_{(u,x)} f(u,x) = \sum_{(x,v)} f(x,v)$$$, where $$$(u,x)$$$ and $$$(x,v)$$$ are edges in the graph.

Due to the skew symmetry property, every edge in the network has a reverse edge.

$$$c(x,y) - f(x,y)$$$ is called the residual capacity $$$\text{rest}(i,j)$$$ of an edge.

The flow of a network is
$$$\sum_{(S,v)} f(S,v)$$$, where $$$(S,v)$$$ are edges in the graph.

A network flow can be likened to a pipeline system for transporting tap water: the source continuously produces water, the sink continuously stores water, and each intermediate node only transports water without storing it.

There are many valid flow functions $$$f$$$ for a network. The flow function that maximizes the network's flow (as defined above) is called the maximum flow.

Maximum Flow Template Problem

Edmonds-Karp Augmenting Path Algorithm

An augmenting path is a path from $$$S$$$ to $$$T$$$ where every edge has a residual capacity greater than 0.

We can push an additional flow of $$$\min\operatorname{rest}(x,y)$$$ along this path, so the maximum flow increases by this value.
For each edge $$$(x,y)$$$ on the path, its residual capacity $$$\operatorname{rest}(x,y)$$$ decreases by $$$\min\operatorname{rest}(x,y)$$$.

Sometimes, some edges need to support inflows from other edges, so we don't necessarily have to reduce the residual capacity by the full $$$\min\operatorname{rest}(x,y)$$$.

Would we have to use DFS, leading to exponential time complexity?

Clever people came up with a solution: constructing reverse edges (flow retraction operation).

When an augmenting path is found, we increase the residual capacity of the reverse edge $$$\operatorname{rest}(y,x)$$$ by $$$\min\operatorname{rest}(x,y)$$$.

This allows for "regret" — if we find a better augmenting path that includes reverse edges, we can restore the residual capacity of the forward edges.

This still satisfies the flow conservation property.

This way, we can cancel out edges from suboptimal augmenting paths.

By repeatedly finding and augmenting paths (with regret), we can find the maximum flow.

How to Find Augmenting Paths?

BFS or DFS both work.

However, I implemented BFS because it's simpler.

We keep updating the augmenting paths as long as we can find them, until no more augmenting paths exist.

Time complexity: $$$O(nm^2)$$$ (proven on oi-wiki).

In practice, it rarely reaches this upper bound for most networks.

Thus, this algorithm can generally handle networks of scale $$$10^3 - 10^4$$$.

Code: ```cpp

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; // tot=1 to access reverse edges via XOR int head[10010],to[20010],nxt[20010],val[20010],tot=1; void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; } int maxflow,dis[10010],pre[10010]; bool vis[10010];

bool bfs(){ queueq; memset(vis,0,sizeof vis); vis[s]=1,dis[s]=1e18; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]){ // Skip if visited or no residual capacity if(vis[to[i]] || !val[i]) continue; // Find the minimum residual capacity on the path dis[to[i]]=min(dis[u],val[i]); // Record the edge to reconstruct the path pre[to[i]]=i,vis[to[i]]=1; q.push(to[i]); // Early return if sink is reached if(to[i]==t) return 1; } } return 0; }

void update(){// Update the path int x=t; while(x!=s){ int i=pre[x]; val[i]-=dis[t]; // Update reverse edge using XOR val[i^1]+=dis[t]; // Traverse back along the reverse edge x=to[i^1]; } // Update the maximum flow maxflow+=dis[t]; }

signed main() { cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; // Add forward edge and reverse edge (initial flow 0) add(u,v,w),add(v,u,0); } // Augment until no more paths exist while(bfs()) update(); cout<<maxflow; return 0; } ```

Dinic's Algorithm

The EK algorithm may traverse the entire residual network in one BFS but only finds one augmenting path.

So how can we find multiple augmenting paths with a single BFS?

We can use BFS to layer the graph, then use DFS on the layered graph (edges only go from layer $$$u$$$ to $$$u+1$$$) to find augmenting paths.

Specifically: start from the source $$$S$$$, perform DFS down the layered graph to the sink $$$T$$$.

When backtracking, update the augmenting path like EK, and check if a node can support the flow if it has multiple augmenting paths.

Current Arc Optimization

This is the key reason Dinic is faster than EK.

First, a node $$$u$$$ may be traversed multiple times.

When enumerating edges of $$$u$$$, if the outgoing flow equals the incoming flow, return immediately — further updates would violate flow conservation.

Thus, when we traverse $$$u$$$ the second time, we skip edges that have already been fully augmented.

This optimization guarantees the time complexity.

Why Layer the Graph?

First, the number of layers in the layered graph is at most the number of nodes $$$n$$$.

As proven on oi-wiki, with the above optimizations, the time complexity of a single augmentation is $$$O(n)$$$ (where $$$n$$$ is the number of nodes).

Total time complexity: $$$O(n^2m)$$$.

In practice, it rarely reaches this upper bound for most networks.

Thus, this algorithm can generally handle networks of scale $$$10^4 - 10^5$$$.

Note: Without current arc optimization, the time complexity degrades to that of EK.

Code: ```cpp // Dinic's Algorithm

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; int head[10010],to[20010],nxt[20010],val[20010],tot=1; void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; } int maxflow,dis[10010],now[10010]; bool vis[10010];

bool bfs(){ queueq; memset(vis,0,sizeof vis); vis[s]=1,dis[s]=0,now[s]=head[s]; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]){ if(vis[to[i]] || !val[i]) continue; // Reset current arc now[to[i]]=head[to[i]]; dis[to[i]]=dis[u]+1,vis[to[i]]=1; q.push(to[i]); if(to[i]==t) return 1; } } return 0; }

int dinic(int x,int flow){ // Reached sink if(x==t) return flow; // Remaining flow to push int rest=flow; // Enumerate edges (stop if rest=0) for(int i=now[x];i && rest;i=nxt[i]){ // Current arc optimization now[x]=i; // Skip non-layered edges or edges with no residual capacity if(dis[to[i]]!=dis[x]+1 || !val[i]) continue; // Augment along the edge int v=dinic(to[i],min(rest,val[i])); // Prune: this path is no longer augmentable if(!v) dis[to[i]]=0; // Update residual capacity val[i]-=v,val[i^1]+=v; // Update remaining flow rest-=v; } // Return the actual pushed flow return flow-rest; }

signed main() { cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w),add(v,u,0); } int flow=0; // Augment until no more layered graphs while(bfs()) // Augment all possible paths in the layered graph while(flow=dinic(s,1e18)) maxflow+=flow; cout<<maxflow; return 0; } ``` Exercise

Bipartite Graph 1

What is a Bipartite Graph?

Definition 1: An undirected graph where nodes can be divided into two disjoint sets such that no two nodes within the same set are adjacent.
Definition 2: An undirected graph with no odd-length cycles.

Thus, we can use a coloring algorithm to determine if a graph is bipartite and assign nodes to their respective sets.

Steps: 1. For each node, if its adjacent nodes are uncolored, color them with a different color. 2. After coloring, use DFS to propagate the coloring. 3. If an adjacent node is already colored, check if it has a different color. If not, the graph is not bipartite. 4. Note: The graph may be disconnected.

Exercise: [NOIP2010 Improvement Group] Imprisoning Criminals (https://www.luogu.com.cn/problem/P1525) (solve with binary search transformation).

Maximum Matching in Bipartite Graphs

The maximum number of edges that can be selected in a bipartite graph such that each node is incident to at most one selected edge.

Hungarian Algorithm

A simple algorithm for finding maximum matching in bipartite graphs.

Template: Maximum Matching in Bipartite Graphs

Approach: - Represent left-set nodes as $$$u$$$ and right-set nodes as $$$v+n$$$. - Although bipartite graphs are undirected, converting them to directed graphs (left to right) simplifies processing. - For each left-set node, check if it can be matched to a right-set node without invalidating existing matches (we can reassign existing matches). - Use DFS to implement this: 1. For a right-set node the left node can match to: — If the right node is unmatched, match them directly. — Otherwise, try to reassign the original left node paired with this right node. 2. Use a vis array to avoid reprocessing nodes in the same DFS call.

Code: ```cpp

include<bits/stdc++.h>

using namespace std; int n,m,e; int head[1010],to[50010],nxt[50010],tot; void add(int u,int v){ to[++tot]=v; nxt[tot]=head[u]; head[u]=tot; } // Matching of right-set nodes to left-set nodes int mat[1010]; // Visited array for DFS bool vis[1010];

bool dfs(int x){ for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]){ vis[to[i]]=1; // Either the right node is unmatched, or we can reassign its match if(!mat[to[i]] || dfs(mat[to[i]])){ mat[to[i]]=x; return 1; } } return 0; }

int main() { cin>>n>>m>>e; for(int i=1;i<=e;i++){ int u,v; cin>>u>>v; add(u,v+n); } int ans=0; // Iterate over left-set nodes for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(dfs(i)) ans++; } cout<<ans; return 0; } ``` Swapping the left and right sets yields the same answer.

Time complexity: $$$O(nm)$$$ (traverse the entire graph $$$n$$$ times).

Dinic's Algorithm for Bipartite Matching

Conclusion 1

On unit-capacity networks, Dinic's algorithm has a time complexity of $$$O(m\min(\sqrt{m},n^{\frac{2}{3}}))$$$.

Conclusion 2

On bipartite graphs with only unit-capacity edges, Dinic's time complexity is $$$O(m\sqrt{n})$$$.

Approach: 1. Create virtual source $$$S$$$ and sink $$$T$$$. 2. Connect $$$S$$$ to all left-set nodes (capacity 1). 3. Connect all right-set nodes to $$$T$$$ (capacity 1). 4. The maximum flow of this network equals the maximum matching of the bipartite graph (easily proven).

This solves bipartite matching in $$$O(m\sqrt{n})$$$ time.

Code: ```cpp // Dinic's Algorithm for Bipartite Matching

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,e,s,t; int head[10010],to[200010],nxt[200010],val[200010],tot=1; void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; } int maxflow,dis[10010],now[10010]; bool vis[10010];

bool bfs(){ queueq; memset(vis,0,sizeof vis); vis[s]=1,dis[s]=0,now[s]=head[s]; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]){ if(vis[to[i]] || !val[i]) continue; now[to[i]]=head[to[i]]; dis[to[i]]=dis[u]+1,vis[to[i]]=1; q.push(to[i]); if(to[i]==t) return 1; } } return 0; }

int dinic(int x,int flow){ if(x==t) return flow; int rest=flow; for(int i=now[x];i && rest;i=nxt[i]){ now[x]=i; if(dis[to[i]]!=dis[x]+1 || !val[i]) continue; int v=dinic(to[i],min(rest,val[i])); if(!v) dis[to[i]]=0; val[i]-=v,val[i^1]+=v; rest-=v; } return flow-rest; }

signed main() { cin>>n>>m>>e; s=0,t=n+m+1; for(int i=1;i<=e;i++){ int u,v; cin>>u>>v; add(u,v+n,1),add(v+n,u,0); } // Connect source to left-set nodes for(int i=1;i<=n;i++) add(0,i,1),add(i,0,0); // Connect right-set nodes to sink for(int i=1;i<=m;i++) add(i+n,n+m+1,1),add(n+m+1,i+n,0); int flow=0; while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; cout<<maxflow; return 0; } ```

Network Flow 2

Max-Flow Min-Cut Theorem

A cut of a network is a set of edges whose removal disconnects $$$S$$$ from $$$T$$$. The min cut is the cut with the smallest sum of edge capacities.

Theorem: In any network, the maximum flow equals the min cut.

Proof: 1. First, min cut $$$\ge$$$ max flow (if min cut $$$ \lt $$$ max flow, an augmenting path still exists). 2. Let $$$A$$$ be the set of nodes reachable from $$$S$$$ in the residual network after finding the max flow, and $$$B$$$ be the unreachable set. 3. Max flow = total flow out of $$$S$$$ = total flow out of $$$A$$$ = total flow into $$$A$$$. 4. For any edge $$$(x,y)$$$ where $$$x \in A$$$ and $$$y \in B$$$: — $$$(x,y)$$$ must be saturated (flow = capacity). — For edge $$$(y,x)$$$, flow must be $$$0$$$ (otherwise, $$$(x,y)$$$ would have residual capacity $$$ \gt 0$$$). 5. The sum of capacities of all $$$(x,y)$$$ (from $$$A$$$ to $$$B$$$) equals the min cut (these edges disconnect $$$S$$$ from $$$T$$$). 6. Thus, min cut = max flow.

Q.E.D.

Exercise

Dinic's Algorithm Optimizations

Template: Max Flow Enhanced Version / Preflow Push

I don't know what preflow push is. Let's try some "black magic" optimizations.

Optimization 1: Bitwise Segmentation

Dinic's algorithm is slow when flow values vary significantly.

Approach: 1. Split flow values into groups by binary bits: group $$$p$$$ contains values $$$2^p \le x \lt 2^{p+1}$$$. 2. Enumerate groups from largest to smallest, run Dinic on each group. 3. Keep edges from previous groups for subsequent runs.

This reduces time complexity to $$$O(nm\log C)$$$ (proof omitted).

Code: ```cpp // Dinic with Bitwise Segmentation

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; int head[10010],to[240010],nxt[240010],val[240010],tot=1; void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; } int maxflow,dis[10010],now[10010]; bool vis[10010];

bool bfs(){// BFS for layering queueq;// STL queue memset(vis,0,sizeof vis); vis[s]=1,dis[s]=0,now[s]=head[s]; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]){ if(vis[to[i]] || !val[i]) continue; now[to[i]]=head[to[i]]; dis[to[i]]=dis[u]+1,vis[to[i]]=1; q.push(to[i]); // Early return if sink is reached if(to[i]==t) return 1; } } return 0; }

int dinic(int x,int flow){ if(x==t) return flow; int rest=flow; for(int i=now[x];i && rest;i=nxt[i]){ now[x]=i;// Current arc optimization if(dis[to[i]]!=dis[x]+1 || !val[i]) continue; int v=dinic(to[i],min(rest,val[i])); if(!v) dis[to[i]]=0; val[i]-=v,val[i^1]+=v; rest-=v; } return flow-rest; }

struct node{ int u,v,w; }e[120010];

signed main() { ios::sync_with_stdio(0); cin>>n>>m>>s>>t; // Store edges first for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w; // Enumerate bits from highest to lowest for(int i=30;i>=0;i--){ int p=(1<<i); // Add edges in current group for(int j=1;j<=m;j++) if(e[j].w>=p && e[j].w<p*2) add(e[j].u,e[j].v,e[j].w),add(e[j].v,e[j].u,0); // Run Dinic and accumulate answer int flow=0; while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; // Keep edges for next groups } cout<<maxflow; return 0; } ``` Score: 68 pts (https://www.luogu.com.cn/record/169178727)

Optimization 2: Reverse Edge Retention (Self-named)

Since Optimization 1 processes part of the graph first, we can extend this idea.

Reverse edges impact efficiency (flow going back).

Approach: 1. Run Dinic once without considering reverse edges (but track their weights). 2. Add reverse edges and run Dinic again.

This significantly improves efficiency.

Code: ```cpp // Dinic with Reverse Edge Retention

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; int head[10010],to[240010],nxt[240010],val[240010],tot=1; vectore[10010];

void add(int u,int v,int w){// Modified add function to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; // Store edges for Dinic e[u].push_back(tot); // Add reverse edge (not used in Dinic initially, but updated) to[++tot]=u,val[tot]=0; nxt[tot]=head[v]; head[v]=tot; }

int maxflow,dis[10010],now[10010]; bitset<10010>vis; bool Flag=0; int Q[10010],H,T;

inline bool bfs(){ H=1,T=0; for(int i=1;i<=n;i++) vis[i]=0; vis[s]=1,dis[s]=0,now[s]=0; Q[++T]=s; while(H<=T){ int u=Q[H++]; for(int i=0;i<e[u].size();i++){ if(vis[to[e[u][i]]] || !val[e[u][i]]) continue; now[to[e[u][i]]]=0; dis[to[e[u][i]]]=dis[u]+1,vis[to[e[u][i]]]=1; Q[++T]=to[e[u][i]]; if(to[e[u][i]]==t) return 1; } } return 0; }

int dinic(int x,int flow){ if(x==t) return flow; int rest=flow; for(int i=now[x];i<e[x].size() && rest;i++){ now[x]=i; if(dis[to[e[x][i]]]!=dis[x]+1 || !val[e[x][i]]) continue; int v=dinic(to[e[x][i]],min(rest,val[e[x][i]])); if(!v) dis[to[e[x][i]]]=0; val[e[x][i]]-=v,val[e[x][i]^1]+=v; rest-=v; } return flow-rest; }

struct node{ int u,v,w; }E[120010];

signed main() { ios::sync_with_stdio(0); cin>>n>>m>>s>>t; for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w; // Enumerate bits for(int i=30;i>=0;i--){ int p=(1<<i); int kt=tot; // Add edges in current group for(int j=1;j<=m;j++) if(E[j].w>=p && E[j].w<p*2) add(E[j].u,E[j].v,E[j].w); // First Dinic run (without reverse edges) int flow=0; while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; // Add reverse edges for(int j=1;j<=m;j++){ if(E[j].w>=p && E[j].w<p*2){ kt+=2; e[E[j].v].push_back(kt); } } // Second Dinic run (with reverse edges) while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; } cout<<maxflow; return 0; } ``` Score: 84 pts (https://www.luogu.com.cn/record/169372193)

Optimization 3: Bit Compression (Optimization for Optimization 1)

Process 3 bits at a time instead of 1. This reduces the number of iterations but increases the flow range per iteration.

Efficiency depends on data, but this passes the problem.

Code: ```cpp // Dinic with Bit Compression (3 bits at a time)

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; int head[1210],to[240010],nxt[240010],val[240010],tot=1; vectore[1210];

void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; e[u].push_back(tot); to[++tot]=u,val[tot]=0; nxt[tot]=head[v]; head[v]=tot; }

int maxflow,dis[1210],now[1210]; bitset<1210>vis; bool Flag=0; int Q[1210],H,T;

inline bool bfs(){ H=1,T=0; for(int i=1;i<=n;i++) vis[i]=0; vis[s]=1,dis[s]=0,now[s]=0; Q[++T]=s; while(H<=T){ int u=Q[H++]; for(int i=0;i<e[u].size();i++){ if(vis[to[e[u][i]]] || !val[e[u][i]]) continue; now[to[e[u][i]]]=0; dis[to[e[u][i]]]=dis[u]+1,vis[to[e[u][i]]]=1; Q[++T]=to[e[u][i]]; if(to[e[u][i]]==t) return 1; } } return 0; }

int dinic(int x,int flow){ if(x==t) return flow; int rest=flow; for(int i=now[x];i<e[x].size() && rest;i++){ now[x]=i; if(dis[to[e[x][i]]]!=dis[x]+1 || !val[e[x][i]]) continue; int v=dinic(to[e[x][i]],min(rest,val[e[x][i]])); if(!v) dis[to[e[x][i]]]=0; val[e[x][i]]-=v,val[e[x][i]^1]+=v; rest-=v; } return flow-rest; }

struct node{ int u,v,w; }E[120010];

signed main() { ios::sync_with_stdio(0); cin>>n>>m>>s>>t; for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w; // Enumerate 3 bits at a time for(int i=30;i>=0;i-=3){ int p=(1<<i); int kt=tot; // Add edges in current group (8x range) for(int j=1;j<=m;j++) if(E[j].w>=p && E[j].w<p*8) add(E[j].u,E[j].v,E[j].w); // First Dinic run int flow=0; while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; // Add reverse edges for(int j=1;j<=m;j++){ if(E[j].w>=p && E[j].w<p*8){ kt+=2; e[E[j].v].push_back(kt); } } // Second Dinic run while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; } cout<<maxflow; return 0; } ``` AC Record: (https://www.luogu.com.cn/record/169372645)

Time complexity: "black magic" (depends on data).

My Solution

Cost Flow

Template: Minimum Cost Maximum Flow

Edmonds-Karp Algorithm for Cost Flow

Replace BFS with SPFA to find the augmenting path with the minimum total cost.

The cost of reverse edges is the negative of the forward edges.

Code omitted (EK is too inefficient).

Time complexity: $$$O(n^2m^2)$$$ (works for random data due to loose upper bound).

Dinic's Algorithm for Cost Flow

Replace BFS layering with SPFA to find the shortest path in terms of cost.

An edge $$$(u,v,w,cost)$$$ is part of the layered graph only if $$$dis_v = dis_u + cost$$$.

Other logic is similar to standard Dinic.

Note: Zero-cost cycles may cause infinite loops in DFS, so add a vis array to prevent this.

Code: ```cpp // Dinic's Algorithm for Minimum Cost Maximum Flow

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; int head[10010],to[100010],nxt[100010],val[100010],cost[100010],tot=1; void add(int u,int v,int w,int c){ to[++tot]=v,val[tot]=w,cost[tot]=c; nxt[tot]=head[u]; head[u]=tot; } int maxflow,mincost,dis[10010],now[10010]; bool vis[10010];

bool spfa(){// SPFA for cost-based layering listq; memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); vis[s]=dis[s]=0,now[s]=head[s]; q.push_back(s); while(!q.empty()){ int u=q.front(); q.pop_front(); vis[u]=0; for(int i=head[u];i;i=nxt[i]){ now[to[i]]=head[to[i]]; if(!val[i]) continue; if(dis[to[i]]>dis[u]+cost[i]){ dis[to[i]]=dis[u]+cost[i]; if(vis[to[i]]) continue; vis[to[i]]=1; // SLF optimization (search online for details) if(dis[to[i]]<dis[q.empty() ? 0 :q.front()]) q.push_front(to[i]); else q.push_back(to[i]); } } } // Clear vis for DFS memset(vis,0,sizeof vis); return dis[t]<dis[0]/2; }

int dinic(int x,int flow){ vis[x]=1;// Prevent cycles if(x==t) return flow;// Reached sink int rest=flow; for(int i=now[x];i && rest;i=nxt[i]){ now[x]=i; // Skip invalid edges or visited nodes if(dis[to[i]]!=dis[x]+cost[i] || !val[i] || vis[to[i]]) continue; int v=dinic(to[i],min(rest,val[i])); if(!v) dis[to[i]]=dis[0]; // Update flow and cost val[i]-=v,val[i^1]+=v,mincost+=cost[i]*v; rest-=v; } vis[x]=1; return flow-rest; }

struct node{ int u,v,w,c; }e[100010];

signed main() { ios::sync_with_stdio(0); cin>>n>>m>>s>>t; for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w>>e[i].c; // Add edges (reverse edge cost is negative) for(int i=1;i<=m;i++) add(e[i].u,e[i].v,e[i].w,e[i].c),add(e[i].v,e[i].u,0,-e[i].c); int flow=0; while(spfa()) while(flow=dinic(s,1e18)) maxflow+=flow; cout<<maxflow<<" "<<mincost; return 0; } ``` Time complexity: $$$O(nmc)$$$.

Exercises: This Problem and Its Enhanced Version.

Important Notes: - Cost flow uses SPFA + DFS with a vis array, so avoid the "black magic" optimizations used for standard Dinic. - Bitwise optimization leads to incorrect time complexity, and reverse edge retention leads to incorrect answers.

Bipartite Graph 2

Kőnig's Theorem

Kőnig's Theorem states that in bipartite graphs, the size of the minimum vertex cover equals the size of the maximum matching.

A minimum vertex cover is the smallest set of nodes such that every edge is incident to at least one node in the set.

The proof is analogous to the Max-Flow Min-Cut Theorem (omitted).

Maximum Independent Set in Bipartite Graphs

An independent set is a set of nodes with no edges between them.

Theorem: The size of the maximum independent set in a bipartite graph equals the total number of nodes minus the size of the maximum matching.

Proof: - This is equivalent to removing the minimum number of nodes to eliminate all edges (minimum vertex cover). - Thus, maximum independent set = total nodes — minimum vertex cover = total nodes — maximum matching.

Q.E.D.

Weighted Matching in Bipartite Graphs

Weighted matching refers to finding the maximum matching with the maximum/minimum sum of edge weights.

Cost Flow Solution

Solve it using cost flow like standard maximum matching (max flow with cost optimization).

KM Algorithm

Main Problem

Standard cost flow will not pass this problem — use KM instead.

The KM algorithm solves weighted maximum matching for bipartite graphs with perfect matching (both sets have $$$n$$$ nodes, and maximum matching size is $$$n$$$).

Here: - Left-set nodes: $$$1$$$ to $$$n$$$. - Right-set nodes: $$$n+1$$$ to $$$2n$$$.

Vertex Labels

Denoted as $$$l$$$, a label for each node satisfying $$$l_x + l_y \ge w(x,y)$$$ for all edges $$$(x,y)$$$.

Equality Subgraph

The subgraph consisting of all edges where $$$l_x + l_y = w(x,y)$$$.

Theorem: If the equality subgraph contains a perfect matching of the original graph, this perfect matching is the maximum weight matching of the original graph.

The total weight of this matching is $$$\sum_{i=1}^{2n} l_i$$$ (optimal since $$$l_x + l_y \ge w(x,y)$$$ for all edges).

Alternating Tree

In the Hungarian algorithm, the tree traversed when a node fails to find a match is called an alternating tree (alternates between matched and unmatched edges).

KM Algorithm Steps

1. Initialize labels:

• Left-set nodes: $$$l_i = \max{w(i,j) | (i,j) \in E}$$$.
• Right-set nodes: $$$l_i = 0$$$.

1. Expand the equality subgraph iteratively:

• Use the Hungarian algorithm to find matches in the equality subgraph.
• If a match fails, adjust labels:
  • Subtract $$$\Delta$$$ from labels of all left-set nodes in the alternating tree.
  • Add $$$\Delta$$$ to labels of all right-set nodes in the alternating tree.
  • $$$\Delta = \min{l_i + l_j - w(i,j) | i \in \text{alternating tree}, j \notin \text{alternating tree}}$$$.

1. Optimization: Skip traversing previously visited alternating trees (time complexity reduces to $$$O(n^3)$$$).

Code: ```cpp

include<bits/stdc++.h>

using namespace std;

define int long long

int n,e; int head[1010],to[250010],val[250010],nxt[250010],tot; inline void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; } // Matching of right-set nodes to left-set nodes int mat[1010]; bool vis[1010]; // Vertex labels, delta values, parent pointers int l[1010],upd[1010],fa[1010];

inline bool dfs(int x,int f){ vis[x]=1; for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]){ // Edge is in equality subgraph if(l[x]+l[to[i]]==val[i]){ vis[to[i]]=1,fa[to[i]]=f; // Find a match if(!mat[to[i]] || dfs(mat[to[i]],to[i])){ mat[to[i]]=x; return 1; } } // Update delta for non-equality edges else if(upd[to[i]]>l[x]+l[to[i]]-val[i]) upd[to[i]]=l[x]+l[to[i]]-val[i],fa[to[i]]=f; } return 0; }

inline int KM(){ // Initialize labels for(int i=1;i<=n;i++){ l[i]=-1e15,l[i+n]=0; for(int j=head[i];j;j=nxt[j]) l[i]=max(l[i],val[j]); } // Process each left-set node for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); memset(fa,0,sizeof fa); memset(upd,0x3f,sizeof upd); int p=0;mat[0]=i; while(mat[p]){ int del=1e18; // Try to find a match if(dfs(mat[p],p)) break; // Calculate delta for(int j=n+1;j<=2*n;j++) if(!vis[j] && upd[j]<del) del=upd[j],p=j; // Adjust labels for(int j=1;j<=n;j++) if(vis[j]) l[j]-=del; for(int j=n+1;j<=2*n;j++) if(vis[j]) l[j]+=del; else upd[j]-=del; vis[p]=1; } // Update matching while(p){ mat[p]=mat[fa[p]]; p=fa[p]; } } // Calculate total weight int ans=0; for(int i=n+1;i<=2*n;i++) for(int j=head[mat[i]];j;j=nxt[j]) if(to[j]==i) ans+=val[j]; return ans; }

signed main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>e; for(int i=1;i<=e;i++){ int u,v,w; cin>>u>>v>>w; add(u,v+n,w); } cout<<KM()<<"\n"; // Output matching results for(int i=1;i<=n;i++) cout<<mat[n+i]<<" "; return 0; } ```

Network Flow 3

Feasible Flow with Lower and Upper Bounds (No Source/Sink)

Given a network where each edge's flow is between $$$p(u,v)$$$ (lower bound) and $$$q(u,v)$$$ (upper bound), determine if a flow function exists that satisfies flow conservation for all nodes.

Approach: 1. Naive idea: Use $$$q(u,v)-p(u,v)$$$ as edge capacities and set flow to $$$f(u,v)+p(u,v)$$$ — incorrect (lower bounds may not balance). 2. Correct approach: — Create new source $$$S'$$$ and sink $$$T'$$$. — Define: — $$$inp(u) = \sum_{(i,u)} p(i,u)$$$ (total lower bound inflow to $$$u$$$). — $$$outp(u) = \sum_{(u,i)} p(u,i)$$$ (total lower bound outflow from $$$u$$$). — $$$d(u) = inp(u) - outp(u)$$$. — If $$$d(u) \gt 0$$$: add edge $$$S' \to u$$$ with capacity $$$d(u)$$$. — If $$$d(u) \lt 0$$$: add edge $$$u \to T'$$$ with capacity $$$-d(u)$$$. — Run max flow from $$$S'$$$ to $$$T'$$$: feasible flow exists iff the flow is saturated (equals total $$$d(u) \gt 0$$$).

Feasible Flow with Lower and Upper Bounds (With Source/Sink)

Given a network where each edge's flow is between $$$p(u,v)$$$ and $$$q(u,v)$$$, determine if a flow function exists that satisfies flow conservation for all nodes except $$$S$$$ and $$$T$$$.

Approach: - Add an edge $$$T \to S$$$ with lower bound $$$0$$$ and upper bound $$$\infty$$$. - Convert to the no-source/sink case (above). - If feasible, the flow of the edge $$$T \to S$$$ equals the feasible flow from $$$S$$$ to $$$T$$$.

Maximum Flow with Lower and Upper Bounds (With Source/Sink)

1. Find a feasible flow using the above method.
2. Remove the edge $$$T \to S$$$ from the residual network.
3. Run max flow from $$$S$$$ to $$$T$$$ — total flow = feasible flow + max flow from step 3.

Minimum Flow with Lower and Upper Bounds (With Source/Sink)

1. Find a feasible flow using the above method.
2. Remove the edge $$$T \to S$$$ from the residual network.
3. Run max flow from $$$T$$$ to $$$S$$$ — total flow = feasible flow — max flow from step 3.

Note: If all $$$d(u) = 0$$$, the minimum flow is $$$0$$$.

Code for U556791: ```cpp // Dinic for Flow with Lower/Upper Bounds

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t,S,T; int head[100010],to[100010],nxt[100010],val[100010],tot=1; void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; } int maxflow,dis[100010],now[100010]; bool vis[100010];

bool bfs(){ queueq; memset(vis,0,sizeof vis); vis[s]=1,dis[s]=0,now[s]=head[s]; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]){ if(vis[to[i]] || !val[i]) continue; now[to[i]]=head[to[i]]; dis[to[i]]=dis[u]+1,vis[to[i]]=1; q.push(to[i]); if(to[i]==t) return 1; } } return 0; }

int dinic(int x,int flow){ if(x==t) return flow; int rest=flow; for(int i=now[x];i && rest;i=nxt[i]){ now[x]=i; if(dis[to[i]]!=dis[x]+1 || !val[i]) continue; int v=dinic(to[i],min(rest,val[i])); if(!v) dis[to[i]]=0; val[i]-=v,val[i^1]+=v; rest-=v; } return flow-rest; }

int V[100010],_val[100010];

signed main() { cin>>n>>m>>S>>T; s=0,t=n+1; for(int i=1;i<=m;i++){ int u,v,p,q; cin>>u>>v>>p>>q; // Add edge with capacity q-p add(u,v,q-p),add(v,u,0); // Update d(u) = inp — outp V[u]-=p,V[v]+=p; } int sum=0; bool flag=0; // Add edges for lower bounds for(int i=1;i<=n;i++) if(V[i]>0) add(s,i,V[i]),add(i,s,0),flag=1,sum+=V[i]; else if(V[i]<0) add(i,t,-V[i]),add(t,i,0),flag=1; // Add edge T->S (infinite capacity) add(T,S,1e15),add(S,T,0); int flow=0; // Check feasibility while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; if(maxflow<sum) cout<<"A clever xzy~~~"; else{ // Save residual capacities for(int i=1;i<=tot;i++) _val[i]=val[i]; // Calculate minimum flow (T->S max flow) s=T,t=S; int ans=val[tot]; val[tot]=val[tot^1]=0; maxflow=0; while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; if(flag) cout<<ans-maxflow-1<<" ";else cout<<"-1 "; // Calculate maximum flow (S->T max flow) swap(s,t); for(int i=1;i<=tot;i++) val[i]=_val[i]; val[tot]=val[tot^1]=0; maxflow=0; while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; cout<<ans+maxflow+1; } return 0; } ```

Exercises for Flow with Lower/Upper Bounds

• U556791
• P4043
• P4843
• P5192
• P5258

Extension

• P4486

Properties of Flow with Lower/Upper Bounds

Not strictly flow with lower/upper bounds — arbitrary initial flow assignment: 1. For an edge with flow range $$$[L_i, R_i]$$$, set flow to arbitrary $$$x$$$. 2. Replace the edge with: — Edge $$$u_i \to v_i$$$ with capacity $$$R_i - x$$$. — Edge $$$v_i \to u_i$$$ with capacity $$$x - L_i$$$. 3. Update $$$inp$$$ and $$$outp$$$ accordingly (arbitrary initial flow property).

Cost Flow with Lower/Upper Bounds

1. Set initial flow to $$$L_i$$$ (lower bound).
2. Set initial cost to $$$L_i \times c_i$$$ (cost per unit flow).
3. Solve using standard cost flow.

Cost Flow with Negative Cycles

1. For edges with positive cost: process normally.
2. For edges with negative cost:

• Use arbitrary initial flow property to set flow to upper bound $$$R_i$$$.
• Replace edges as above.

1. Solve using flow with lower/upper bounds.

Cost Flow with Negative Cycles and Lower/Upper Bounds

1. For edges with positive cost: process normally.
2. For edges with negative cost:

• Set flow to upper bound $$$R_i$$$.
• Replace edges using arbitrary initial flow property.

1. Solve using flow with lower/upper bounds.

Applications of Network Flow (Graph Construction)

Key techniques: 1. Node Splitting: Split a node into an "in-node" and "out-node" (common for node capacity constraints). 2. Cost Flow for Conditional Contributions: Use cost flow to model contributions (e.g., first $$$k$$$ passes give $$$v$$$ reward, no reward afterward). 3. Stores and Trash Bins: Nodes as "stores" (produce flow) or "trash bins" (consume flow) — not necessarily source/sink. 4. Min Cut Modeling: Model selection problems as disconnecting nodes (set non-cuttable edges to $$$\infty$$$).

Back to P1004: Cost Flow Modeling

Problem: Two paths from top-left to bottom-right, no repeated point collection.

Modeling: 1. Node Splitting: Split each node $$$(i,j)$$$ into in-node and out-node. 2. Point Weight to Edge Weight: — Edge in-node $$$\to$$$ out-node: capacity $$$1$$$, cost = point weight (collect once). — Edge in-node $$$\to$$$ out-node: capacity $$$1$$$, cost = $$$0$$$ (pass through again without collection). 3. Adjacency Edges: Connect out-node of $$$(i,j)$$$ to in-node of adjacent nodes (right/down). 4. Run cost flow (max flow = 2, max cost = total collected points).

Code: ```cpp // Dinic for P1004 (Cost Flow)

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; int head[20010],to[100010],nxt[100010],val[100010],cost[100010],tot=1; void add(int u,int v,int w,int c){ to[++tot]=v,val[tot]=w,cost[tot]=c; nxt[tot]=head[u]; head[u]=tot; } int maxflow,maxcost,dis[20010],now[20010]; bool vis[20010];

bool spfa(){ listq; memset(dis,-0x3f,sizeof dis); memset(vis,0,sizeof vis); vis[s]=dis[s]=0,now[s]=head[s]; q.push_back(s); while(!q.empty()){ int u=q.front(); q.pop_front(); vis[u]=0; for(int i=head[u];i;i=nxt[i]){ now[to[i]]=head[to[i]]; if(!val[i]) continue; if(dis[to[i]]<dis[u]+cost[i]){ dis[to[i]]=dis[u]+cost[i]; if(vis[to[i]]) continue; vis[to[i]]=1; q.push_back(to[i]); } } } memset(vis,0,sizeof vis); return dis[t]>dis[0]/2; }

int dinic(int x,int flow){ vis[x]=1; if(x==t) return flow; int rest=flow; for(int i=now[x];i && rest;i=nxt[i]){ now[x]=i; if(dis[to[i]]!=dis[x]+cost[i] || !val[i] || vis[to[i]]) continue; int v=dinic(to[i],min(rest,val[i])); if(!v) dis[to[i]]=dis[0]; val[i]-=v,val[i^1]+=v,maxcost+=cost[i]*v; rest-=v; } return flow-rest; }

struct node{ int u,v,w,c; }e[100010];

namespace Input{ int a[110][110]; void main() { int u=0,v=0,w=0; while(true){ cin>>u>>v>>w; if(u==0 && v==0 && w==0) return; a[u][v]=w; } } }

// Get node ID (in-node: k=0, out-node: k=1) int get(int x,int y,int k){ return (x-1)*n+y+k*n*n; }

int k;

signed main() { ios::sync_with_stdio(0); cin>>n; k=2; s=1,t=2*n*n; Input::main(); // Node splitting and edge creation for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ // Collect point (capacity 1, cost = point weight) add(get(i,j,0),get(i,j,1),1,Input::a[i][j]),add(get(i,j,1),get(i,j,0),0,-Input::a[i][j]); // Pass through (capacity k-1=1, cost 0) add(get(i,j,0),get(i,j,1),k-1,0),add(get(i,j,1),get(i,j,0),0,0); // Connect to down node if(i<n) add(get(i,j,1),get(i+1,j,0),k,0),add(get(i+1,j,0),get(i,j,1),0,0); // Connect to right node if(j<n) add(get(i,j,1),get(i,j+1,0),k,0),add(get(i,j+1,0),get(i,j,1),0,0); } } int flow=0; while(spfa()) while(flow=dinic(s,1e18)) maxflow+=flow; cout<<maxcost; return 0; } ```

Exercise: P2045

Example: P4313 Problem: Maximize satisfaction by choosing arts/science for students (with group satisfaction).

Modeling: 1. Source $$$S$$$ = choose arts, sink $$$T$$$ = choose science. 2. Individual Satisfaction: — $$$S \to (i,j)$$$: capacity = art satisfaction (cut = lose art satisfaction). — $$$(i,j) \to T$$$: capacity = science satisfaction (cut = lose science satisfaction). 3. Group Satisfaction: — For art group satisfaction: — Add virtual node $$$A_{i,j}$$$. — $$$S \to A_{i,j}$$$: capacity = art group satisfaction. — $$$A_{i,j} \to (i,j)$$$ and adjacent nodes: capacity = $$$\infty$$$ (must cut all if any node chooses science). — For science group satisfaction: — Add virtual node $$$B_{i,j}$$$. — $$$B_{i,j} \to T$$$: capacity = science group satisfaction. — $$$(i,j)$$$ and adjacent nodes $$$\to B_{i,j}$$$: capacity = $$$\infty$$$ (must cut all if any node chooses art). 4. Answer = total satisfaction — min cut.

Code: ```cpp // Dinic for P4313 (Min Cut)

include<bits/stdc++.h>

using namespace std;

define int long long

int n,m,s,t; int head[30010],to[2000010],nxt[2000010],val[2000010],tot=1; void add(int u,int v,int w){ to[++tot]=v,val[tot]=w; nxt[tot]=head[u]; head[u]=tot; } int maxflow,dis[30010],now[30010]; bool vis[30010];

bool bfs(){ queueq; memset(vis,0,sizeof vis); vis[s]=1,dis[s]=0,now[s]=head[s]; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]){ if(vis[to[i]] || !val[i]) continue; now[to[i]]=head[to[i]]; dis[to[i]]=dis[u]+1,vis[to[i]]=1; q.push(to[i]); if(to[i]==t) return 1; } } return 0; }

int dinic(int x,int flow){ if(x==t) return flow; int rest=flow; for(int i=now[x];i && rest;i=nxt[i]){ now[x]=i; if(dis[to[i]]!=dis[x]+1 || !val[i]) continue; int v=dinic(to[i],min(rest,val[i])); if(!v) dis[to[i]]=0; val[i]-=v,val[i^1]+=v; rest-=v; } return flow-rest; }

int ar[110][110],sc[110][110],sa[110][110],ss[110][110],S; // Get node ID for (i,j) inline int get(int i,int j){ return (i-1)*m+j; }

signed main() { cin>>n>>m; s=0,t=3*n*m+1; // Art satisfaction (S -> (i,j)) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>ar[i][j]; S+=ar[i][j]; add(s,get(i,j),ar[i][j]),add(get(i,j),s,0); } // Science satisfaction ((i,j) -> T) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>sc[i][j]; S+=sc[i][j]; add(get(i,j),t,sc[i][j]),add(t,get(i,j),0); } // Art group satisfaction (virtual node) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>sa[i][j]; S+=sa[i][j]; add(s,get(i,j)+n*m,sa[i][j]),add(get(i,j)+n*m,s,0); // Virtual node -> (i,j) (infinite capacity) add(get(i,j)+n*m,get(i,j),1e9),add(get(i,j),get(i,j)+n*m,0); // Connect to adjacent nodes if(i>1) add(get(i,j)+n*m,get(i-1,j),1e9),add(get(i-1,j),get(i,j)+n*m,0); if(j>1) add(get(i,j)+n*m,get(i,j-1),1e9),add(get(i,j-1),get(i,j)+n*m,0); if(i<n) add(get(i,j)+n*m,get(i+1,j),1e9),add(get(i+1,j),get(i,j)+n*m,0); if(j<m) add(get(i,j)+n*m,get(i,j+1),1e9),add(get(i,j+1),get(i,j)+n*m,0); } // Science group satisfaction (virtual node) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>ss[i][j]; S+=ss[i][j]; add(get(i,j)+2*n*m,t,ss[i][j]),add(t,get(i,j)+2*n*m,0); // (i,j) -> virtual node (infinite capacity) add(get(i,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j),0); // Connect adjacent nodes to virtual node if(i>1) add(get(i-1,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i-1,j),0); if(j>1) add(get(i,j-1),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j-1),0); if(i<n) add(get(i+1,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i+1,j),0); if(j<m) add(get(i,j+1),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j+1),0); } // Calculate min cut int flow=0; while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow; // Answer = total satisfaction — min cut cout<<S-maxflow; return 0; } ```