网络流–最大流dinic模板

标准的大白书式模板，除了变量名并不一样……在主函数中只需要用到 init 函数、add 函数以及 mf 函数

 #include<stdio.h>                //差不多要加这么些头文件
 #include<string.h>
 #include<queue>
 #include<vector>
 #include<algorithm>
 using namespace std;
 const int maxm=+;        //点的总数
 const int INF=0x3f3f3f3f; struct edge{             //弧的结构体，变量：弧的出发点、结束点、容量、流量
     int from,to,c,f;
     edge(int a,int b,int m,int n):from(a),to(b),c(m),f(n){}
 }; struct dinic{
     int m,s,t;                    //边数、源点标号、汇点标号
     vector<edge>e;        //边
     vector<int>g[maxm];    //g[i][j]表示第i个点出发的第j条边在e中的编号
     bool vis[maxm];
     int d[maxm],cur[maxm];    //d为源点到点的距离，cur为当前遍历到的边
     void init(int n){                //初始化，n为点数量（标号0～n-1）
         for(int i=;i<n+;i++)g[i].clear();
         e.clear();
     }
     void add(int a,int b,int v){        //加入弧和反向弧
         e.push_back(edge(a,b,v,));    //正向弧容量v，反向弧容量0
         e.push_back(edge(b,a,,));
         m=e.size();
         g[a].push_back(m-);
         g[b].push_back(m-);
     }
     bool bfs(){
         memset(vis,,sizeof(vis));
         queue<int>q;
         q.push(s);
         d[s]=;
         vis[s]=;
         while(!q.empty()){
             int u=q.front();q.pop();
             for(int i=;i<g[u].size();i++){
                 edge tmp=e[g[u][i]];
                 if(!vis[tmp.to]&&tmp.c>tmp.f){
                     vis[tmp.to]=;
                     d[tmp.to]=d[u]+;
                     q.push(tmp.to);
                 }
             }
         }
         return vis[t];
     }
     int dfs(int x,int a){
         if(x==t||a==)return a;
         int flow=,f;
         for(int& i=cur[x];i<g[x].size();i++){
             edge &tmp=e[g[x][i]];
             if(d[x]+==d[tmp.to]&&(f=dfs(tmp.to,min(a,tmp.c-tmp.f)))>){
                 tmp.f+=f;
                 e[g[x][i]^].f-=f;
                 flow+=f;
                 a-=f;
                 if(a==)break;
             }
         }
         if(!flow)d[x]=-;
         return flow;
     }
     int mf(int s,int t){                //在主函数中使用的函数，求s到t的最大流
         this->s=s;
         this->t=t;
         int flow=;
         while(bfs()){
             memset(cur,,sizeof(cur));
             flow+=dfs(s,INF);
         }
         return flow;
     }
 };