网络流之最大流（dinic算法模板+模板题）

dinic算法：时间复杂度O(), n 代表点的个数，m 代表边的个数。

const int N=1e5+5;
struct Edge{int to,w,next;
}edge[N*2];//双向边 
int head[N],d[N],cur[N];
int n,m,s,t,cnt=1;// 从 2 , 3 开始配对 
void add(int u,int v,int w){edge[++cnt]={v,w,head[u]};head[u]=cnt;
}
bool bfs(){// 对点分层，找增广路 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=edge[i].next){int v=edge[i].to;if(d[v]==0 && edge[i].w){d[v]=d[u]+1;q.push(v);if(v==t) return true;}}}return false;
}
int dfs(int u,int flow){if(u==t) return flow;int sum=0;for(int i=cur[u];i;i=edge[i].next){cur[u]=i;// 当前弧优化 int v=edge[i].to;if(d[v]==d[u]+1 && edge[i].w){int f=dfs(v,min(flow,edge[i].w));edge[i].w-=f;edge[i^1].w+=f;// 更新残留网 sum+=f; // 累加 u 的流出流量 flow-=f;// 减少 u 的剩余流量 if(!flow) break;// 余量优化 }}if(!sum) d[u]=0;//残枝优化 return sum;
}
int dinic(){// 累加可行流 int ans=0;while(bfs()){memcpy(cur,head,sizeof head);//将 head 数组复制给 cur 数组 ans+=dfs(s,1e18);//初始值定为正无穷大 }return ans;
}

模板题：

思路：直接套用模板即可。（就比模板多了个加边）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e5+5;
struct Edge{int to,w,next;
}edge[N*2];
int head[N],d[N],cur[N];
int n,m,s,t,cnt=1;
void add(int u,int v,int w){edge[++cnt]={v,w,head[u]};head[u]=cnt;
}
bool bfs(){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=edge[i].next){int v=edge[i].to;if(d[v]==0 && edge[i].w){d[v]=d[u]+1;q.push(v);if(v==t) return true;}}}return false;
}
int dfs(int u,int flow){if(u==t) return flow;int sum=0;for(int i=cur[u];i;i=edge[i].next){cur[u]=i;int v=edge[i].to;if(d[v]==d[u]+1 && edge[i].w){int f=dfs(v,min(flow,edge[i].w));edge[i].w-=f;edge[i^1].w+=f;sum+=f;flow-=f;if(!flow) break;}}if(!sum) d[u]=0;return sum;
}
int dinic(){int ans=0;while(bfs()){memcpy(cur,head,sizeof head);ans+=dfs(s,1e18);}return ans;
}
signed main()
{IOScin >> 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);}cout << dinic() << endl;return 0;
}