Dinic最大流 || Luogu P3376 【模板】网络最大流

题面：【模板】网络最大流

代码：

 #include<cstring>

 #include<cstdio>

 #include<iostream>

 #define min(a,b) ((a)<(b)?(a):(b))

 using namespace std;

 inline int rd(){

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-; c=getchar();}

     while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

     return f*x;

 }

 const int maxn=(1e4)+,maxm=(1e5)+;

 int num_edge=-,edge_head[maxn],N,M,S,T,w,u,v,Q[maxn<<],f1,f2,Dep[maxn],Cur[maxn];

 struct Edge{int to,nx,dis;}edge[maxm<<];

 inline void Add_edge(int from,int to,int dis){

     edge[++num_edge].nx=edge_head[from];

     edge[num_edge].to=to;

     edge[num_edge].dis=dis;

     edge_head[from]=num_edge;

     return;

 }

 inline bool Bfs(){

     memset(Dep,,sizeof(Dep));

     Dep[S]=;

     f1=f2=;

     Q[f2++]=S;

     while(f1<f2){

         int x=Q[f1++];

         for(int i=edge_head[x];i!=-;i=edge[i].nx){

             int y=edge[i].to;

             if(edge[i].dis&&Dep[y]==){

                 Dep[y]=Dep[x]+;

                 Q[f2++]=y;

             }

         }

     }

     if(Dep[T])return ;

     return ;

 }

 inline int Dfs(int x,int fw){

     if(x==T)return fw;

     for(int &i=Cur[x];i!=-;i=edge[i].nx){

         int y=edge[i].to;

         if(Dep[y]==Dep[x]+&&edge[i].dis){

             int p=Dfs(y,min(fw,edge[i].dis));

             if(p>){

                 edge[i].dis-=p;

                 edge[i^].dis+=p;

                 return p;

             }

         }

     }

     return ;

 }

 inline int Dinic(){

     int ans=;

     while(Bfs()){

         for(int i=;i<=N;i++)Cur[i]=edge_head[i];

         while(int k=Dfs(S,<<))ans+=k;

     }

     return ans;

 }

 int main(){

     memset(edge_head,-,sizeof(edge_head));

     N=rd();M=rd();S=rd();T=rd();

     for(int i=;i<=M;i++){

         u=rd();v=rd();w=rd();

         Add_edge(u,v,w);

         Add_edge(v,u,);

     }

     printf("%d\n",Dinic());

     return ;

 }

---

By:AlenaNuna