2171. EK求最大流

结果: ACCEPTED
通过了 10/10个数据
运行时间: 39 ms
运行空间: 476 KB
提交时间: 5天前
码字时间: 2 分钟 22.268 秒

C++
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N=1005; const int M=20005; const int INF=0x3fffffff; int n,m,S,T; int h[N],e[M],ne[M],w[M],idx=1; int d[N],pre[N],q[N],hh,tt; bool vis[N]; void add(int a,int b,int c) { e[++idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx; } bool bfs() { memset(vis,false,sizeof vis); vis[S]=true,d[S]=INF; *q=S,hh=tt=0; while(hh<=tt) { int t=q[hh++]; for(int i=h[t];i;i=ne[i]) if(!vis[e[i]]&&w[i]) { pre[e[i]]=i; vis[e[i]]=true; d[e[i]]=min(d[t],w[i]); if(e[i]==T)return true; q[++tt]=e[i]; } } return false; } int main() { scanf("%d%d%d%d",&n,&m,&S,&T); for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,0); } int maxflow=0; while(bfs()) { maxflow+=d[T]; for(int i=T;i!=S;i=e[pre[i]^1]) w[pre[i]]-=d[T],w[pre[i]^1]+=d[T]; } printf("%d\n",maxflow); return 0; }