![image]()
标准模板
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=210,M=5e3+10;
int n,m,s,t,d[N],cur[N],vis[N];
int h[N],e[M<<1],ne[M<<1],id=1;//从2,3开始配对
LL c[M<<1];
void add(int u,int v,LL w){++id;e[id]=v;ne[id]=h[u];c[id]=w;h[u]=id;
}LL dfs(int u,LL mf){//多路增广if(u==t)return mf;LL sum=0;for(int i=cur[u];i;i=ne[i]){cur[u]=i;//当前弧优化int v=e[i];if(d[v]==d[u]+1&&c[i]){LL f=dfs(v,min(mf,c[i]));sum+=f;//累加u的流出流量c[i]-=f;c[i^1]+=f;//更新残留网mf-=f;//减少u的剩余流量if(mf==0)//余量优化break;}}if(sum==0)//残枝优化d[u]=0;return sum;
}bool bfs(){//对点分层，找增广路memset(d,0,sizeof(d));queue<int> q;q.push(s);d[s]=1;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i;i=ne[i]){int v=e[i];if(d[v]==0&&c[i]){d[v]=d[u]+1;q.push(v);if(v==t)return true;}}}return false;
}LL dinic(){//累加可行流LL flow=0;while(bfs()){memcpy(cur,h,sizeof(h));flow+=dfs(s,1e9);}return flow;
}void mincut(int u){vis[u]=1;for(int i=h[u];i;i=ne[i]){int v=e[i];if(!vis[v]&&c[i])mincut(v);}
}void reset_edges(){//每条边是成对存储，正边id为偶数，反边id为奇数for(int i=2;i<=id;i++){if(i&1){c[i]=0;}else{if(c[i])c[i]=1e9;elsec[i]=1;}}
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){LL u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,0);}//最小割cout<<dinic()<<endl;//最小割划分mincut(s);//访问过的点为S集合for(int i=1;i<=n;i++){if(vis[i])cout<<i<<' ';}cout<<endl;//没访问过的点为T集合for(int i=1;i<=n;i++){if(!vis[i])cout<<i<<' ';}cout<<endl;//求最小割的最少边数//重建边时应当把第一遍dinic中剩余容量为0的正向边的边权设为1，//其他正向边设为无穷大，反向边都设为零，//因为只有流满的边才是最小割中的边。reset_edges();cout<<dinic()<<endl;return 0;
}
模板题：洛谷p1344
code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=210,M=5e3+10;
int n,m,s,t,d[N],cur[N],vis[N];
int h[N],e[M<<1],ne[M<<1],id=1;//从2,3开始配对
LL c[M<<1];
void add(int u,int v,LL w){++id;e[id]=v;ne[id]=h[u];c[id]=w;h[u]=id;
}LL dfs(int u,LL mf){//多路增广if(u==t)return mf;LL sum=0;for(int i=cur[u];i;i=ne[i]){cur[u]=i;//当前弧优化int v=e[i];if(d[v]==d[u]+1&&c[i]){LL f=dfs(v,min(mf,c[i]));sum+=f;//累加u的流出流量c[i]-=f;c[i^1]+=f;//更新残留网mf-=f;//减少u的剩余流量if(mf==0)//余量优化break;}}if(sum==0)//残枝优化d[u]=0;return sum;
}bool bfs(){//对点分层，找增广路memset(d,0,sizeof(d));queue<int> q;q.push(s);d[s]=1;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i;i=ne[i]){int v=e[i];if(d[v]==0&&c[i]){d[v]=d[u]+1;q.push(v);if(v==t)return true;}}}return false;
}LL dinic(){//累加可行流LL flow=0;while(bfs()){memcpy(cur,h,sizeof(h));flow+=dfs(s,1e9);}return flow;
}void mincut(int u){vis[u]=1;for(int i=h[u];i;i=ne[i]){int v=e[i];if(!vis[v]&&c[i])mincut(v);}
}void reset_edges(){//每条边是成对存储，正边id为偶数，反边id为奇数for(int i=2;i<=id;i++){if(i&1){c[i]=0;}else{if(c[i])c[i]=1e9;elsec[i]=1;}}
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);// cin>>n>>m>>s>>t;cin>>n>>m;s=1;t=n;for(int i=1;i<=m;i++){LL u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,0);}//最小割// cout<<dinic()<<endl;cout<<dinic()<<' ';//最小割划分// mincut(s);//访问过的点为S集合// for(int i=1;i<=n;i++){// if(vis[i])// cout<<i<<' ';// }// cout<<endl;//没访问过的点为T集合// for(int i=1;i<=n;i++){// if(!vis[i])// cout<<i<<' ';// }// cout<<endl;//求最小割的最少边数//重建边时应当把第一遍dinic中剩余容量为0的正向边的边权设为1，//其他正向边设为无穷大，反向边都设为零，//因为只有流满的边才是最小割中的边。reset_edges();cout<<dinic()<<endl;return 0;
}
