网络流dinic模板，邻接矩阵+链式前向星

//这个是邻接矩阵的
#include<iostream>

#include<queue>

#include<string.h>

#include<stdio.h>

#include<algorithm>

using namespace std;

const int maxn=;

const int inf=0x3f3f3f;

int N;

int depth[maxn];

int a[maxn][maxn];

bool bfs(int s,int e)//广搜求深度

{

    queue<int>q;

    memset(depth,-,sizeof(depth));//初始-1

    depth[s]=;

    q.push(s);

    while(!q.empty())

    {

        int now=q.front();

        q.pop();

        for(int i=;i<=N;i++)

        {

            if(depth[i]==-&&a[now][i])//两点有路，并且未搜过

            {

                depth[i]=depth[now]+;

                q.push(i);

            }

        }

    }

    return depth[e]>;

 }

 int dfs(int now,int e,int nowflow)

 {

     if(now==N) return nowflow;//如果搜到最后

     int findflow=;

     for(int i=;i<=N;i++)

     {

         if(a[now][i]&&depth[i]==depth[now]+)//有路，并且为下一节点

         {

             findflow=dfs(i,e,min(nowflow,a[now][i]));//继续dfs

             if(findflow)

             {

                 a[now][i]-=findflow;

                 a[i][now]+=findflow;

                 return findflow;

             }

         }

     }

     if(!findflow) depth[now]=-;//炸点优化

     return false;

 }

 int dinic(int s,int e)

 {

     int maxflow=;

     while(bfs(s,e))

     maxflow+=dfs(s,e,<<);

     return maxflow;

 }

链式前向星

没听说过的同学 戳这里

#include<bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f;

const int maxn = 1e5+;

struct node{

    int v,w,next;

    node(int v1=,int w1=,int next1=):v(v1),w(w1),next(next1){}

};

node e[maxn<<];

int head[maxn];

int tot;

int N,E;//顶点数和边数

int dep[maxn];//求深度

int cur[maxn]//当前弧优化

void init()

{

    tot=;

    memset(head,-,sizeof(head));

}

void add(int u,int v,int w)

{

    e[tot].v=v;

    e[tot].w=w;

    e[tot].next=head[u];

    head[u]=tot++;

    //反向边

    e[tot].v=u;

    e[tot].w=;

    e[tot].next=head[v];

    head[v]=tot++;

}

//bfs分层图

bool bfs(int ss,int ee)

{

    memset(dep,-,sizeof(dep));

    queue<int>q;

    dep[ss]=;

    q.push(ss);

    while(!q.empty())

    {

        int now=q.front();

        q.pop();

        for(int i=head[now];i!=-;i=e[i].next)

        {

            if(dep[e[i].v]==- && e[i].w>)

            {

                dep[e[i].v]=dep[now]+;

                q.push(e[i].v);

            }

        }

    }

    return dep[ee]!=-;

}

//dfs搜索增广路径，now搜索顶点 ee终点 nowflow当前最大流

int dfs(int now,int ee,int nowflow)

{

    // 搜索到终点或者  最大流为0

    if(now==ee||nowflow==) return nowflow;

    //useflow 可用流量 达到nowflow时不再增加

    //maxflow 递归深搜时的最大流

    int useflow=,maxflow;

    //&i=cur[now] 为cur[now]起了个别名，为当前弧优化，每次更新cur[now];

    for(int &i=cur[now]; i != - ; i = e[i].next)

    {

        if(e[i].w >  && dep[e[i].v] == dep[now] + )

        {

            maxflow = dfs(e[i].v, ee, min(nowflow-useflow, e[i].w));

            if(maxflow>)

            {

                e[i].w-=maxflow;

                e[i^].w+=maxflow;

                useflow+=maxflow;

                if(uswflow == nowflow) return nowflow;

            }

        }

    }

    if(!useflow) dep[now]=-;

    return useflow;

}

int dinic(int ss,int ee)

{

    int ans=;

    while(bfs(ss,ee))

    {

        for(int i=;i<=N;i++)

        cur[i]=head[i];

        ans+=dfs(ss,ee,inf);

    }

    return ans;

}