网络流-最大流 Dinic模板

 #include <bits/stdc++.h>

 using namespace std;

 #define MP make_pair

 #define PB push_back

 #define ls first

 #define rs second

 typedef long long LL;

 typedef pair<int,int> PII;

 const double eps=1e-;

 const double pi=acos(-1.0);

 const int K=1e5+;

 const int mod=1e9+;

 vector<pair<int,int>>mp[K];

 int n,m,cnt,flow[K*],deep[K],cur[K];

 int bfs(int s,int t)

 {

     queue<int>q;

     memset(deep,,sizeof deep);

     q.push(s),deep[s]=;

     while(!q.empty())

     {

         int u=q.front();q.pop();

         for(auto &it:mp[u])

         if(!deep[it.ls]&&flow[it.rs])

         {

             deep[it.ls]=deep[u]+;

             q.push(it.ls);

             if(it.ls==t)

                 return ;

         }

     }

     return ;

 }

 int dfs(int x,int d,int t)

 {

     if(x==t) return d;

     for(int i=cur[x];i<mp[x].size();cur[x]=++i)

     {

         int u=mp[x][i].ls,v=mp[x][i].rs;

         if(deep[u]==deep[x]+&&flow[v])

         {

             int td=min(d,dfs(u,min(d,flow[v]),t));

             if(!td) continue;

             flow[v]-=td;

             flow[v^]+=td;

             return td;

         }

     }

     return ;

 }

 int dinic(int s,int t)

 {

     int ret=,d;

     while(bfs(s,t))

     {

         memset(cur,,sizeof cur);

         while(d=dfs(s,mod,t))    ret+=d;

     }

     return ret;

 }

 int main(void)

 {

     while(~scanf("%d%d",&m,&n))

     {

         cnt=;

         memset(mp,,sizeof mp);

         for(int i=,u,v,w;i<m;i++)

         {

             scanf("%d%d%d",&u,&v,&w);

             flow[cnt]=w,flow[cnt+]=;

             mp[u].PB(MP(v,cnt++));

             mp[v].PB(MP(u,cnt++));

         }

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

     }

     return ;

 }