最大流模板（含三种模板）

最后一种最快， 前两种彼此彼此

紫书模板

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

struct edge{
    int from, to, cap, flow;
};

int n, m;
vector<edge> edges;   //边数的两倍
vector<int> mp[maxn]; //邻接表，mp[i][j]表示节点i的第j条边在e数组中的序号
int dis[maxn];        //从起点的i的距离
int cur[maxn];        //当前弧

void add(int s, int t, int c) {
    edges.push_back((edge){s, t, c, 0});
    edges.push_back((edge){t,s,0,0});
    int m=edges.size();
    mp[s].push_back(m-2);
    mp[t].push_back(m-1);
}


bool bfs(int s, int t) {
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(s);
    while(q.size()) {
        int now=q.front(); q.pop();
        if(now==t) return 1;
        for(int i=0; i<mp[now].size(); ++i) {
            edge &v=edges[mp[now][i]];
            if(dis[v.to]<0&&v.cap>v.flow) {
                dis[v.to]=dis[now]+1;
                q.push(v.to);
            }
        }
    }
    return 0;
}

int dfs(int now, int t, int f) {
    if(now==t||!f) return f;
    int flow=0, d;
    for(int &i=cur[now]; i<mp[now].size(); ++i) {
        edge &v=edges[mp[now][i]];
        if(dis[now]+1==dis[v.to]&&(d=dfs(v.to,t,min(f,v.cap-v.flow)))>0) {
            v.flow+=d;
            edges[mp[now][i]^1].flow-=d;
            flow+=d;
            f-=d;
            if(!f) break;
        }
    }
    if(!flow) dis[now]=-2;
    return flow;
}

int dinic(int s, int t) {
    int flow=0;
    while(bfs(s,t)) {
        memset(cur,0,sizeof(cur));
        flow+=dfs(s,t,1e6);
    }
    return flow;
}

int main() {
    //读入数据+建边
    return 0;
}

白书模板

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

const int INF=2e9+10;

struct edge{
    int to, cap, rev;
};

int N, M;

vector<edge> mp[210];
int dis[210], cur[210];

void init() {
    for(int i=0; i<M; ++i) {
        mp[i].clear();
    }
}

void add(int s, int t, int c) {
    mp[s].push_back((edge){t,c,mp[t].size()});
    mp[t].push_back((edge){s,0,mp[s].size()-1});
}

bool bfs(int s, int t) {
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    dis[s]=0;
    q.push(s);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        if(now==t) return 1;
        for(int i=0; i<mp[now].size(); ++i) {
            edge &v=mp[now][i];
            if(v.cap>0 && dis[v.to]<0) {
                dis[v.to]=dis[now]+1;
                q.push(v.to);
            }
        }
    }
    return 0;
}

int dfs(int now, int t, int f) {
    if(now==t||!f) return f;
    int flow=0;
    for(int &i=cur[now]; i<mp[now].size(); ++i) {
        edge &v=mp[now][i];
        if(v.cap>0 && dis[now]+1==dis[v.to]) {
            int d=dfs(v.to, t, min(f,v.cap));
            if(d>0) {
                v.cap-=d;
                mp[v.to][v.rev].cap+=d;
                flow+=d;
                f-=d;
                if(!f) break;
            }
        }
    }
    if(!flow) dis[now]=-2;
    return flow;
}

int dinic(int s, int t) {
    int flow=0;
    while(bfs(s,t)) {
        memset(cur,0,sizeof(cur));
        int f;
        while((f=dfs(s,t,INF))>0) {
            flow+=f;
        }
    }
    return flow;
}

int main() {
    while(cin>>N>>M) {
        init();
        for(int i=0; i<N; ++i) {
            int s, e, c;
            cin>>s>>e>>c;
            add(s,e,c);
        }
        printf("%d\n", dinic(1,M));
    }
    return 0;
}

崔神模板

经过部分取舍后

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

const int INF=1e9+7;
const int maxd=50, maxe=500;
int head[maxd], tot;
int S, T;

struct Edge{
    int from, to, cap, next;
    Edge() {}
    Edge(int x, int y, int a, int c):from(x),to(y),cap(a),next(c) {}
}eage[maxe*2];

void add(int x, int y, int a) {
    eage[tot]=Edge(x,y,a,head[x]), head[x]=tot++;
    eage[tot]=Edge(y,x,0,head[y]), head[y]=tot++;
}

bool used[maxd], vis[maxd];
int dis[maxd];
queue<int> q;
int ans=0;

bool spfa() {
    for(int i=0; i<maxd; ++i) used[i]=false, dis[i]=INF, vis[i]=false;
    while(q.size()) q.pop();
    q.push(S);
    used[S]=true;
    dis[S]=0;
    while(q.size()) {
        int u=q.front(); q.pop();
        used[u]=false;
        for(int i=head[u]; ~i; i=eage[i].next) {
            if(eage[i].cap&&dis[eage[i].to]>dis[u]+1) {
                int v=eage[i].to;
                dis[v]=dis[u]+1;
                if(!used[v]) {
                    used[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return (dis[T]<INF);
}

int dfs(int u, int flow) {
    if(u==T || !flow) {
        ans+=flow;
        return flow;
    }
    vis[u]=true;
    int ret=0;
    for(int i=head[u]; ~i; i=eage[i].next) {
        if(!vis[eage[i].to] && eage[i].cap && dis[eage[i].to]==dis[u]+1) {
            int v=eage[i].to;
            int newf=dfs(v,min(flow,eage[i].cap));
            eage[i].cap-=newf;
            eage[i^1].cap+=newf;
            ret+=newf;
            if(!flow) break;
        }
    }
    if(!ret) dis[u]=-1;
    return ret;
}

int Dinic() {
    ans=0;
    while(spfa()) dfs(S,INF);
    return ans;
}

int N, M;
int a[22][22];
void init() {
    register int i;
    for(i=0; i<maxd; ++i) head[i]=-1;
    tot=0;
}

int main() {
    
    return 0;
}

最小费用流