Introduction

The max-flow min-cut theorem is a cornerstone of combinatorial optimization, providing a powerful framework for modeling a wide range of problems. While algorithms like Dinic’s are standard for computing maximum flows, their time complexity—often bounded by $$$\operatorname{O}({|V|}^2|E|)$$$ or $$$\operatorname{O}(|E|\sqrt{|E|})$$$ can become prohibitive for large-scale or specially structured graphs.

This article explores an alternative strategy: instead of applying a generic flow algorithm, we directly analyze the min-cut formulation. The min-cut problem seeks the minimum total capacity of edges whose removal disconnects the source $$$s$$$ from the sink $$$t$$$. Formally, this is expressed as:

$$$ \min_{P,s\in P\land t\notin P}\{\sum_{u\in P,v\notin P}C(u,v)\} $$$

By reformulating this combinatorial problem as a mathematical optimization task, we can often exploit the specific structure of the graph to derive highly efficient, custom-tailored solutions. This approach transforms a graph algorithm problem into a mathematical one, which can be significantly faster for certain problem classes.

Examples

ABC332G

At first I'd like to say ABC332G is the task that made me think if I can solve mincut problems in this way.

In the task we make a graph for example $$$1$$$ like this,and similar for others:

we are tasked with a distribution problem that can be modeled as a min-cut. The constraints are too large for a direct application of Dinic’s algorithm, necessitating a more analytical approach.So we try to use maths and get($$$SETA$$$ for the nodes that represents balls and $$$SETB$$$ for boxes,$$$u_i$$$ as node for $$$i$$$-th colour,$$$v_i$$$ for $$$i$$$-th box):

$$$ \begin{aligned} \operatorname{maxflow}(G) &= \operatorname{mincut}(G)\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i + sum_{v_i \in P\cup SETB}B_i + sum_{u_i\in P\cup SETA,v_j \in \complement_V P \cup SETB}{i \cdot j}\}\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i + sum_j \min\{B_j,sum_{u_i\in P\cup SETA}{i \cdot j}\}\}\\

&= \min_k\{\min_{P,\sum_{u_i \in P} i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i\} + sum_j \min\{B_j,k \cdot j\}\}\\ \end{aligned} $$$

$$$\sum_j \min\{B_j,k \cdot j\}$$$

can be calculated using prefix sum,and

$$$\min_{P,\sum_{u_i \in P} i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}A_i\}$$$

can be calculated using dynamic planning,so the task is then solved in $$$\operatorname{O}(n^3 + m)$$$.

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[509],b[500009],dp[250009],adds[250009],s[250009],s1[250009];
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i ++){
		scanf("%lld",&a[i]);
	}
	for(int i = 1; i <= m; i ++){
		scanf("%lld",&b[i]);
		long long o = b[i] / i;
		s1[1] += i;
		if(o <= n * (n + 1) / 2){
			s1[o + 1] -= i;
			s[o + 1] += b[i] % i;
		}
	}
	for(int i = 1; i <= n * (n + 1) / 2; i ++){
		s1[i] += s1[i - 1];
		s[i] += s[i - 1] + s1[i];
		adds[i] = s[i];
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0] = 0;
	for(int i = 1; i <= n; i ++){
		for(int j = i * (i + 1) / 2; j >= i; j --)
			dp[j] = min(dp[j],dp[j - i] + a[i]);
	}
 	long long ans = 0x3f3f3f3f3f3f3f3fll;
 	for(int i = 0; i <= n * (n + 1) / 2; i ++)
 		ans = min(ans,dp[n * (n + 1) / 2 - i] + adds[i]);
 	printf("%lld\n",ans);
}

2.ARC125E

For ARC125E,the graph is constructed like this:

and found the task presents another scenario where a direct max-flow computation is infeasible due to large values of $$$N,M,A_i,B_i,C_i$$$, which we has to calculate the mincut:

$$$ \begin{aligned} \operatorname{maxflow}(G) &= \operatorname{mincut}(G)\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i + sum_{v_i \in P\cup SETB}A_i + sum_{u_i\in P\cup SETA,v_j \in \complement_V P \cup SETB}{B_i}\}\\ &= \min_P\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i + sum_j \min\{A_j,sum_{u_i\in P\cup SETA}{B_i}\}\}\\

&= \min_k\{\min_{P,\sum_{u_i \in P} B_i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i\} + sum_j \min\{A_j,k\}\}\\ \end{aligned} $$$

There,

$$$\operatorname{F}(x) = \sum_j\{\min \{A_j,x\} \}$$$

can be deem as an convex function that can be calculated using prefix sums and binary search in $$$\operatorname{O}(n) - \operatorname{O}(\log n)$$$,and

$$$\operatorname{G}(x) = \operatorname{F}(\sum B_i) -\operatorname{F}(\sum B_i — x)$$$

is an lower convex function. And for

$$$\operatorname{H}(k) = \min_{P,\sum_{u_i \in P} B_i = k}\{\sum_{u_i\in\complement_{V}P \cup SETA}C_i\}$$$

,it's proven that we can just calculate

$$$\operatorname{H}(k) + \operatorname{F}(\sum B_i — k)$$$

just on the turning point of the low convex by adjustment.

prove

At last,the convex can be found by sorting the children in a non-decreasing order of $$$\frac{C_i}{B_i}$$$ and adding up the children one by one and solve the task in $$$\operatorname{O}(n\log n)$$$.

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
unsigned long long a[200009],f[200009];
struct child{
	unsigned long long b,c;
	bool operator<(const child &y)const{
		return c * y.b < b * y.c;
	}
}ch[200009]; 
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i ++){
		scanf("%llu",&a[i]);
	}
	sort(a + 1,a + n + 1);
	unsigned long long rsumb = 0;
	for(int i = 1; i <= m; i ++)
		scanf("%llu",&ch[i].b),rsumb += ch[i].b;
	for(int i = 1; i <= m; i ++)
		scanf("%llu",&ch[i].c);
	sort(ch + 1,ch + m + 1);
	for(int i = 1; i <= n; i ++){
		f[i] = f[i - 1] + (a[i] - a[i - 1]) * (n - i + 1);
	}
	auto gtf = [](unsigned long long x) -> unsigned long long{
		int l = 0,r = n + 1;
		while(l + 1 < r){
			int mid = (l + r) >> 1;
			if(a[mid] <= x)
				l = mid;
			else
				r = mid;
		}
		return f[l] + (x - a[l]) * (n - l);
	};
	unsigned long long sumb = 0,sumc = 0,ans = gtf(rsumb);
	for(int i = 1; i <= n; i ++){
		sumb += ch[i].b;
		sumc += ch[i].c;
		ans = min(ans,sumc + gtf(rsumb - sumb));
	}
	printf("%lld\n",ans);
	return 0;
}

CF903G

In 903G - Yet Another Maxflow Problem, we are asked to compute a max-flow value in a dynamic graph. Again, a direct flow algorithm is too slow, but the min-cut formulation reveals a tractable mathematical structure:

$$$ min_{i,j}\{A_i + B_j + \sum_{x_k \le i,y_k \ge j}z_k\} = min_i \{a_i + min_j\{B_j + \sum_{x_k \le i,y_k \ge j}z_k\}\} $$$

The $$$j$$$ for getting the $$$\min{B_j + \sum_{x_k \le i,y_k \ge j}z_k}$$$ of each $$$i$$$ is non-decreasing,making it solvable using divide and consequer in $$$\operatorname{O}(n\log^2n)$$$,then for furthur things,we use segment tree and solve it easily.

code

#include<bits/stdc++.h>
using namespace std;
int m,n,q;
long long a[200009],b[200009];
long long bit[200009],seg[800009];
vector<pair<int,int> >ed[200009];
void bit_add(int pl,int val){
	for(int i = pl; i <= n; i += i & (-i))
		bit[i] += val;
}
long long bit_query(int pl){
	long long ans = 0;
	for(int i = pl; i > 0; i &= (i - 1))
		ans += bit[i];
	return ans;
}
void seg_add(int k,int l,int r,int pl,long long val){
	if(l > pl || r < pl)
		return;
	if(l == r){
		seg[k] += val;
		return;
	}
	int m = (l + r) >> 1;
	seg_add(k << 1,l,m,pl,val);
	seg_add((k << 1) | 1,m + 1,r,pl,val);
	seg[k] = min(seg[k << 1],seg[(k << 1) | 1]);
}
void dac(int l,int r,int L,int R){
	if(l > r)
		return;
	int m = (l + r) >> 1;
	for(int i = l; i <= m; i ++){
		for(int j = 0; j < ed[i].size(); j ++){
			bit_add(1,ed[i][j].second);
			bit_add(ed[i][j].first,-ed[i][j].second);
		}
	}
	int M = L;
	long long val = 998244353999911659ll;
	for(int i = L; i <= R; i ++){
		long long o = bit_query(i) + b[i];
		if(o <= val)
			M = i,val = o;
	}
	seg_add(1,1,n,m,val + a[m]);
	for(int i = l; i <= m; i ++){
		for(int j = 0; j < ed[i].size(); j ++){
			bit_add(1,-ed[i][j].second);
			bit_add(ed[i][j].first,ed[i][j].second);
		}
	}
	dac(l,m - 1,L,M);
	for(int i = l; i <= m; i ++){
		for(int j = 0; j < ed[i].size(); j ++){
			bit_add(1,ed[i][j].second);
			bit_add(ed[i][j].first,-ed[i][j].second);
		}
	}
	dac(m + 1,r,M,R);
	for(int i = l; i <= m; i ++){
		for(int j = 0; j < ed[i].size(); j ++){
			bit_add(1,-ed[i][j].second);
			bit_add(ed[i][j].first,ed[i][j].second);
		}
	}
}
int main(){
	scanf("%d %d %d",&n,&m,&q);
	for(int i = 1; i < n; i ++){
		scanf("%lld %lld",&a[i],&b[i + 1]);
	}
	for(int i = 1; i <= m; i ++){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		ed[x].push_back(make_pair(y + 1,z));
	}
	dac(1,n,1,n);
	printf("%lld\n",seg[1]);
	for(int i = 1; i <= q; i ++){
		int x,y;
		scanf("%d %d",&x,&y);
		seg_add(1,1,n,x,y - a[x]);
		a[x] = y;
		printf("%lld\n",seg[1]);
	}
	return 0;
}