当前位置:网站首页>max-flow min-cut
max-flow min-cut
2022-07-06 09:46:00 【C_ eeking】
Max flow min cut
Algorithmic thought
The maximum flow minimum cut mainly uses its theorem to calculate the capacity of the minimum cut , Maximum flow minimum cut theorem : The flow of the largest flow in any network is equal to the capacity of the smallest cut , No detailed proof is given here , Only discuss relevant concepts
cut : Network node division , All nodes are divided into S , T S,T S,T Two sets , Source point s ∈ S s∈S s∈S, Confluence t ∈ T t∈T t∈T, Cut is recorded as C U T ( S , T ) CUT(S,T) CUT(S,T), Like a knife, the node is divided into two parts
Net flow cut : aggregate S S S And collection T T T Between the connected edges , from S S S To T T T The edge of Of Sum of capacity , The minimum cut is the cut with the minimum capacity
if f f f For a stream of the network , C U T ( S , T ) CUT(S,T) CUT(S,T) For any cut of the network , that f f f The flow value of is equal to the net flow of the cut f ( S , T ) f(S,T) f(S,T) And f f f The flow value of does not exceed the capacity of the cut c ( S , T ) c(S,T) c(S,T), All flow values are less than or equal to the cut flow
Maximum flow minimum cut theorem : if f f f Is the largest flow of the network , C U T ( S , T ) CUT(S,T) CUT(S,T) Is the minimum cut of the network , Then the maximum flow value is equal to the minimum cutting capacity
Training
POJ3469
The main idea of the topic : Yes A,B Two core CPU function N A module , Each module has the cost of running on the corresponding core , And there are M Modules need data exchange , If the module is running on the same core , Then the data exchange cost can be ignored , Otherwise, it will cost the given cost , Find the minimum total cost
Ideas : Each module is either in A On , Either in B On , in other words , Last All points will be divided into two sets , This is somewhat similar to a bipartite graph , But these two sets have edges inside , Does not conform to the definition of bipartite graph , So we can consider the minimum cut , Divide all points into two sets , Running on the A The module on is seen as S S S aggregate , stay B See on T T T aggregate , As shown in the figure , The edges cut by the cutting line include S S S The modules in the collection are A Operating costs on a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an,T Assemble in B Operating costs on b 1 , b 2 , … b n b_1,b_2,\dots b_n b1,b2,…bn And the cost of data exchange between modules , The original problem is transformed into the problem of finding the minimum cut , Then it is transformed into the problem of finding the maximum flow
Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=2e4+10;
const int inf=0x3f3f3f3f;
int n,m,head[maxn],cnt,d[maxn];
struct node {
int next,to,cap,flow;
} e[maxn*60];
void Add(int from,int to,int cap,int flow) {
e[cnt].next=head[from];
e[cnt].to=to;
e[cnt].cap=cap;
e[cnt].flow=flow;
head[from]=cnt++;
}
bool BFS(int s,int t) {
// layered
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].to;
if(!d[v]&&e[i].cap>e[i].flow) {
// If the current can be increased
d[v]=d[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int DFS(int u,int flow,int t) {
if(u==t)return flow;
int res=flow;//res Store the current increment value of the current node
for(int i=head[u]; ~i&&res; i=e[i].next) {
// Traverse the adjacent edges satisfying the conditions and increase the current
int v=e[i].to;
if(d[v]==d[u]+1&&e[i].cap>e[i].flow) {
int k=DFS(v,min(res,e[i].cap-e[i].flow),t);// Get the smallest backtracking flow
if(!k)d[v]=0;
e[i].flow+=k;// Increase the flow after obtaining the minimum backtracking flow
e[i^1].flow-=k;
res-=k;// The current increment value decreases , Because the adjacent side has increased the current
}
}
return flow-res;// Return the actual total current increase value
}
int Dinic(int s,int t) {
int ans=0;// Store maximum stream
while(BFS(s,t))ans+=DFS(s,inf,t);
return ans;
}
int main() {
scanf("%d%d",&n,&m);
int s=0,t=n+1;
memset(head,-1,sizeof(head));
for(int i=1; i<=n; i++) {
int a,b;
scanf("%d%d",&a,&b);
Add(s,i,a,0);// Drawing
Add(i,s,0,0);// Residual network edge building
Add(i,t,b,0);
Add(t,i,0,0);
}
while(m--) {
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
Add(a,b,w,0);// Drawing
Add(b,a,0,0);// Residual network edge building
Add(b,a,w,0);
Add(a,b,0,0);
}
printf("%d",Dinic(s,t));
return 0;
}
LuoguP2762
The main idea of the topic : A little
Ideas : Obviously , Instruments and experiments form a bipartite diagram , You can try to solve it with network flow correlation algorithm , Add source connection experiment , Instrument connection junction , There is no capacity constraint between experiment and instrument , The capacity constraint is set to infinity , Pictured , Take the selected experiments and instruments as S aggregate , The rest of the composition T aggregate
Net profit = Selected experimental benefits - The cost of the selected instrument = ∑ E i ∈ S p i − ∑ I k ∈ S c k \sum_{E_i∈S}p_i-\sum_{I_k∈S}c_k ∑Ei∈Spi−∑Ik∈Sck
And the selected experimental income = All experimental benefits - Experimental income is not selected , Then the original formula can be changed to
∑ E i ∈ S p i − ∑ I k ∈ S c k \sum_{E_i∈S}p_i-\sum_{I_k∈S}c_k ∑Ei∈Spi−∑Ik∈Sck
= ∑ i = 1 m p i − ∑ E i ∈ T p i − ∑ I k ∈ S c k =\sum_{i=1}^mp_i-\sum_{E_i∈T}p_i-\sum_{I_k∈S}c_k =∑i=1mpi−∑Ei∈Tpi−∑Ik∈Sck
= ∑ i = 1 m p i − ( ∑ E i ∈ T p i + ∑ I k ∈ S c k ) =\sum_{i=1}^mp_i-(\sum_{E_i∈T}p_i+\sum_{I_k∈S}c_k) =∑i=1mpi−(∑Ei∈Tpi+∑Ik∈Sck)
and ∑ E i ∈ T p i + ∑ I k ∈ S c k \sum_{E_i∈T}p_i+\sum_{I_k∈S}c_k ∑Ei∈Tpi+∑Ik∈Sck Is the sum of the edge capacities on the cutting line , Immediate cut , In order to maximize the total income , Then the minimum cut is required , Then find the maximum flow
Code
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e4;
int n,m,head[maxn],cnt,ve,vi,sum,d[maxn];
struct node {
int to,next,cap,flow;
} e[maxn];
void Add(int from,int to,int cap,int flow) {
e[cnt].cap=cap;
e[cnt].flow=flow;
e[cnt].to=to;
e[cnt].next=head[from];
head[from]=cnt++;
}
bool BFS(int s,int t) {
// layered
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].to;
if(!d[v]&&e[i].cap>e[i].flow) {
// If the current can be increased
d[v]=d[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int DFS(int u,int flow,int t) {
if(u==t)return flow;
int res=flow;//res Store the current increment value of the current node
for(int i=head[u]; ~i&&res; i=e[i].next) {
// Traverse the adjacent edges satisfying the conditions and increase the current
int v=e[i].to;
if(d[v]==d[u]+1&&e[i].cap>e[i].flow) {
int k=DFS(v,min(res,e[i].cap-e[i].flow),t);// Get the smallest backtracking flow
if(!k)d[v]=0;
e[i].flow+=k;// Increase the flow after obtaining the minimum backtracking flow
e[i^1].flow-=k;
res-=k;// The current increment value decreases , Because the adjacent side has increased the current
}
}
return flow-res;// Return the actual total current increase value
}
int Dinic(int s,int t) {
int ans=0;// Store maximum stream
while(BFS(s,t))
ans+=DFS(s,inf,t);
return ans;
}
int main() {
scanf("%d%d",&m,&n);
int s=0,t=n+m+1;
memset(head,-1,sizeof(head));
for(int i=1; i<=m; i++ ) {
scanf("%d",&ve);
Add(s,i,ve,0);
Add(i,s,0,0);
sum+=ve;
char tools[10000];
memset(tools,0,sizeof tools);
cin.getline(tools,10000);
int ulen=0,tool;
while (sscanf(tools+ulen,"%d",&tool)==1) {
// It has been used before scanf After reading, the sponsor agrees to pay for the experiment
//tool It is one of the instruments required for this experiment
// This business , You can save the number read in 、 Handle , Such as connecting sides .
Add(i,tool+m,inf,0);
Add(tool+m,i,0,0);
if (tool==0)
ulen++;
else
while (tool) {
tool/=10;
ulen++;
}
ulen++;
}
}
for(int i=1; i<=n; i++) {
int w;
scanf("%d",&w);
Add(i+m,t,w,0);
Add(t,i+m,0,0);
}
int mx=Dinic(s,t);
for(int i=1; i<=m; i++)
if(d[i])printf("%d ",i);
putchar('\n');
for(int i=m+1; i<=m+n; i++)
if(d[i])printf("%d ",i-m);
putchar('\n');
printf("%d",sum-mx);
return 0;
}
LuoguP4210
The main idea of the topic : A little
Ideas : First of all , Why is the minimum cut , Why the minimum cut is required
According to the meaning , Divide all points into A,B Two large sets , Then the total income is ∑ i ∈ A V a i + ∑ i ∈ B V b i − ∑ i ∈ A V b i − ∑ i ∈ B V a i − ∑ i ∈ A , j ∈ B E i , j + ∑ i ∈ A , j ∈ A E i , j + ∑ i ∈ B , j ∈ B E i , j \sum_{i∈A} V_{a_i}+\sum_{i∈B} V_{b_i}-\sum_{i∈A} V_{b_i}-\sum_{i∈B} V_{a_i}-\sum_{i∈A,j∈B}E_{i,j}+\sum_{i∈A,j∈A}E_{i,j}+\sum_{i∈B,j∈B}E_{i,j} ∑i∈AVai+∑i∈BVbi−∑i∈AVbi−∑i∈BVai−∑i∈A,j∈BEi,j+∑i∈A,j∈AEi,j+∑i∈B,j∈BEi,j, That is to say , All points are in A Medium income + All points are in B Medium income - stay A In the middle of B earnings - stay B In the middle of A earnings - Connect A,B Edge income of set + Connect A Edge income of set + Connect B Edge income of set , Pictured , and ∑ i ∈ A V b i + ∑ i ∈ B V a i + ∑ i ∈ A , j ∈ B E i , j \sum_{i∈A} V_{b_i}+\sum_{i∈B} V_{a_i}+\sum_{i∈A,j∈B}E_{i,j} ∑i∈AVbi+∑i∈BVai+∑i∈A,j∈BEi,j It just corresponds to the edge of the cutting line in the figure , Just the cutting capacity , Then for the best interests of the whole , You need the minimum cut , Then find the maximum flow
The next step is drawing , Divide points into A,B Two parts , Let's make A As S aggregate ,T As B aggregate , Point revenue can be directly connected with the corresponding source point and sink point , What is difficult to deal with is the side benefit of the problem ,
For a given edge , If the side Must belong to A, Then you will lose B Revenue , Then the minimum cut must include This is the edge B The benefits on , For the sake of representation , Put this side on B The income on the market is divided into two , Give two endpoints , That is, there are two more endpoints and two more flows to the sink , The minimum cut either passes through these two flows at the same time , Or don't go through ( On behalf of side return B 了 ), Yes, it must belong to B So is the point of
Next, consider another case of edges , Both belong to A, Also belong to B, If the minimum cut must pass through this edge , Then it must include this side A,B Income and negative income C, That is to connect the two ends , Flow is ABC The benefits and ( Repeat here , Finally, divide the result by 2 that will do )
Because the data may be odd, it cannot be divided into two , Multiply the data by 2 Divide the result by 2
Code
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e4+10;
int n,m,cnt,head[maxn],d[maxn];
struct node {
int to,next,cap,flow;
} e[maxn*80];
void Add(int from,int to,int cap,int flow) {
e[cnt].to=to;
e[cnt].next=head[from];
e[cnt].flow=flow;
e[cnt].cap=cap;
head[from]=cnt++;
}
bool BFS(int s,int t) {
// layered
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].to;
if(!d[v]&&e[i].cap>e[i].flow) {
// If the current can be increased
d[v]=d[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int DFS(int u,int flow,int t) {
if(u==t)return flow;
int res=flow;//res Store the current increment value of the current node
for(int i=head[u]; ~i&&res; i=e[i].next) {
// Traverse the adjacent edges satisfying the conditions and increase the current
int v=e[i].to;
if(d[v]==d[u]+1&&e[i].cap>e[i].flow) {
int k=DFS(v,min(res,e[i].cap-e[i].flow),t);// Get the smallest backtracking flow
if(!k)d[v]=0;
e[i].flow+=k;// Increase the flow after obtaining the minimum backtracking flow
e[i^1].flow-=k;
res-=k;// The current increment value decreases , Because the adjacent side has increased the current
}
}
return flow-res;// Return the actual total current increase value
}
int Dinic(int s,int t) {
int ans=0;// Store maximum stream
while(BFS(s,t))
ans+=DFS(s,inf,t);
return ans;
}
int main() {
scanf("%d%d",&n,&m);
int s=0,t=n+1,sum=0;
memset(head,-1,sizeof(head));
Add(s,1,inf,0),Add(1,s,0,0);
Add(n,t,inf,0),Add(t,n,0,0);
for(int i=2; i<=n-1; i++) {
int v;
scanf("%d",&v);
v*=2;
sum+=v;
Add(s,i,v,0),Add(i,s,0,0);
}
for(int i=2; i<=n-1; i++) {
int v;
scanf("%d",&v);
v*=2;
sum+=v;
Add(i,t,v,0),Add(t,i,0,0);
}
while(m--) {
int x,y,ea,eb,ec;
scanf("%d%d%d%d%d",&x,&y,&ea,&eb,&ec);
ea*=2;
eb*=2;
ec*=2;
sum+=ea+eb;
Add(x,y,(ea/2+eb/2+ec),0),Add(y,x,(ea/2+eb/2+ec),0);
Add(s,x,ea/2,0),Add(x,s,0,0);
Add(s,y,ea/2,0),Add(y,s,0,0);
Add(x,t,eb/2,0),Add(t,x,0,0);
Add(y,t,eb/2,0),Add(t,y,0,0);
}
printf("%d",(sum-Dinic(s,t))/2);
return 0;
}
LuoguP4177
The main idea of the topic : A little
Ideas : If there is no rent / Buy this operation , Then this topic is the classic topic of maximal weighted closed subgraph , The ordinary maximum weight closed subgraph connects the source point with the work , Edge right is income , The machine is connected to the sink , At the expense of edge power , The correspondence between work and machine is infinite , And there is one more rental in this topic , Then there is a kind of edge right that needs to be changed , You can replace infinity with the corresponding leased edge , From the perspective of correctness , When solving the optimal solution , If the total rental cost is lower than the cost of purchasing the machine , The edge weight of the machine and the meeting point will not be full , Prevent the purchase of machines from increasing costs , On the contrary, the edge weight of the machine and the meeting point will be full , Limit costs and prevent multiple rentals
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e6;
const int inf=0x3f3f3f3f;
int n,m,cnt,head[2424],d[2424];// Don't open the memory too much
struct node {
int next,to,cap,flow;
} e[maxn];
void Add(int from,int to,int cap,int flow) {
e[cnt].to=to;
e[cnt].next=head[from];
e[cnt].cap=cap;
e[cnt].flow=flow;
head[from]=cnt++;
}
bool BFS(int s,int t) {
// layered
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].to;
if(!d[v]&&e[i].cap>e[i].flow) {
// If the current can be increased
d[v]=d[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int DFS(int u,int flow,int t) {
if(u==t)return flow;
int res=flow;//res Store the current increment value of the current node
for(int i=head[u]; ~i&&res; i=e[i].next) {
// Traverse the adjacent edges satisfying the conditions and increase the current
int v=e[i].to;
if(d[v]==d[u]+1&&e[i].cap>e[i].flow) {
int k=DFS(v,min(res,e[i].cap-e[i].flow),t);// Get the smallest backtracking flow
if(!k)d[v]=0;
e[i].flow+=k;// Increase the flow after obtaining the minimum backtracking flow
e[i^1].flow-=k;
res-=k;// The current increment value decreases , Because the adjacent side has increased the current
}
}
return flow-res;// Return the actual total current increase value
}
int Dinic(int s,int t) {
int ans=0;// Store maximum stream
while(BFS(s,t))
ans+=DFS(s,inf,t);
return ans;
}
signed main() {
scanf("%lld%lld",&n,&m);
int s=0,t=n+m+1,sum=0;
memset(head,-1,sizeof(head));
for(int i=1; i<=n; i++) {
int x,k;
scanf("%lld%lld",&x,&k);
sum+=x;
Add(s,i,x,0);
Add(i,s,0,0);
while(k--) {
int a,b;
scanf("%lld%lld",&a,&b);
Add(i,a+n,b,0);
Add(a+n,i,0,0);
}
}
for(int i=1; i<=m; i++) {
int y;
scanf("%lld",&y);
Add(i+n,t,y,0);
Add(t,i+n,0,0);
}
printf("%lld",sum-Dinic(s,t));
return 0;
}
summary
The minimum cut model is generally used to solve The most value of multiple constraints under single set of points and double attribution and The maximum value of multiple constraints under two sets of points and multiple matching , It is similar to bipartite graph , But the minimal cut can have edges in the inner set , This is different from the bipartite graph , It also determines that it cannot use the algorithm of bipartite graph in most cases , For the minimum cut problem , You need to find the conditions for dividing the set , Understand why the set should be divided like this , Beyond the basic point weight and edge weight conditions , How to convert other conditions of the problem into flow and construct in the graph , Mapping is always the most critical step , The next steps are actually fixed
reference
边栏推荐
- Mapreduce实例(四):自然排序
- MySQL数据库优化的几种方式(笔面试必问)
- Design and implementation of online snack sales system based on b/s (attached: source code paper SQL file)
- Une grande vague d'attaques à la source ouverte
- May brush question 01 - array
- 【深度學習】語義分割-源代碼匯總
- Elk project monitoring platform deployment + deployment of detailed use (II)
- Global and Chinese market of AVR series microcontrollers 2022-2028: Research Report on technology, participants, trends, market size and share
- [Yu Yue education] reference materials of complex variable function and integral transformation of Shenyang University of Technology
- Redis connection redis service command
猜你喜欢
O & M, let go of monitoring - let go of yourself
《ASP.NET Core 6框架揭秘》样章发布[200页/5章]
大学想要选择学习自动化专业,可以看什么书去提前了解?
Hero League rotation map automatic rotation
单片机实现模块化编程:思维+实例+系统教程(实用程度令人发指)
Hero League rotation chart manual rotation
面试突击62:group by 有哪些注意事项?
Redis connection redis service command
Mapreduce实例(九):Reduce端join
What you have to know about network IO model
随机推荐
CAPL 脚本打印函数 write ,writeEx ,writeLineEx ,writeToLog ,writeToLogEx ,writeDbgLevel 你真的分的清楚什么情况下用哪个吗?
单片机如何从上电复位执行到main函数?
Detailed explanation of cookies and sessions
Activiti7工作流的使用
大学C语言入门到底怎么学才可以走捷径
CANoe仿真功能之自动化序列(Automation Sequences )
单片机实现模块化编程:思维+实例+系统教程(实用程度令人发指)
Workflow - activiti7 environment setup
Global and Chinese market of bank smart cards 2022-2028: Research Report on technology, participants, trends, market size and share
机械工程师和电气工程师方向哪个前景比较好?
五月刷题02——字符串
解决小文件处过多
五月刷题27——图
C#/. Net phase VI 01C Foundation_ 01: running environment, process of creating new C program, strict case sensitivity, meaning of class library
一大波開源小抄來襲
[Yu Yue education] Wuhan University of science and technology securities investment reference
Servlet learning diary 8 - servlet life cycle and thread safety
【深度学习】语义分割:论文阅读:(CVPR 2022) MPViT(CNN+Transformer):用于密集预测的多路径视觉Transformer
五月刷题26——并查集
Mapreduce实例(五):二次排序