网络最大流模板

最小割=最大流
洛谷网络最大流模板题
不断找增广路，使得最大流变大
牛
Ek 时间复杂度o（nm^2），可以处理10的三次方到10的四次方规模的网络;

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s,t;
int head[20005];
int top=1;
struct node1{
   
	int v,val,next;
}node[200005]; 
struct node2{
   
	int v,edge;
}pre[200005];
void add(int v,int u,int val){
   
	node[++top].v=u;
	node[top].val=val;
	node[top].next=head[v];
	head[v]=top;
}
int vis[10005];
bool bfs(){
   
	queue<int> q;
	memset(pre,0,sizeof(pre));
	memset(vis,0,sizeof(vis));
	vis[s]=1;
	q.push(s);
	while(!q.empty()){
   
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=node[i].next){
   
			int d=node[i].v;
			if(!vis[d]&&node[i].val){
   
				pre[d].v=u;
				pre[d].edge=i;
				if(d==t) return 1;
				vis[d]=1;
				q.push(d);
			}
		}
	}
	return 0;
}
int suan(){
   
	int ans=0;
	while(bfs()){
   
		int minn=0x3f3f3f3f;
		for(int i=t;i!=s;i=pre[i].v)
			minn=min(minn,node[pre[i].edge].val);
		for(int i=t;i!=s;i=pre[i].v){
   
			node[pre[i].edge].val-=minn;
			node[pre[i].edge^1].val+=minn;
		}
		ans+=minn;
	}
	return ans;
}
int main(){
   
	scanf("%d%d%d%d",&n,&m,&s,&t);
	while(m--){
   
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,0);
	}
	printf("%d",suan());
	return 0;
}

dinic算法
牛
时间复杂度o(nnm)可以处理10的四次方到10的五次方规模的网络
洛谷P1361
还有个弧优化，没学

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 10005
#define inf 0x3f3f3f3f-1

int tot;
int d[N];
int cnt=1;
int dis[N];
int head[N];
int n,m,s,t;

struct Edge{
   
    int to,nxt,flow;
}edge[4400000];

void add(int x,int y,int z){
   
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    edge[cnt].flow=z;
    head[x]=cnt;
}

bool bfs(){
   
    memset(d,0,sizeof d); d[s]=1;
    std::queue<int> q; q.push(s);
    while(q.size()){
   
        int u=q.front();q.pop();
        for(int i=head[u];i;i=edge[i].nxt){
   
            int to=edge[i].to;
            if(!edge[i].flow) continue;
            if(d[to]) continue;
            d[to]=d[u]+1;
            q.push(to);
            if(to==t) return 1;
        }
    }
    return 0;
}

int dinic(int now,int flow){
   
    if(now==t) return flow;
    int rest=flow;
    for(int i=head[now];i;i=edge[i].nxt){
   
        if(!rest) return flow;
        int to=edge[i].to;
        if(!edge[i].flow) continue;
        if(d[to]!=d[now]+1) continue;
        int k=dinic(to,std::min(rest,edge[i].flow));
        if(!k) d[to]=0;
        rest-=k;
        edge[i].flow-=k;
        edge[i^1].flow+=k;
    }
    return flow-rest;
}

signed main(){
   
    scanf("%d",&n); s=n+1; t=s+1;
    for(int x,i=1;i<=n;i++) scanf("%d",&x),tot+=x,add(s,i,x),add(i,s,0);
    for(int x,i=1;i<=n;i++) scanf("%d",&x),tot+=x,add(i,t,x),add(t,i,0);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
   
        int T,tota,totb;
        scanf("%d%d%d",&T,&tota,&totb);
        tot+=tota+totb;
        add(s,n+2+i,tota); add(n+2+i,s,0);
        add(n+2+i+m,t,totb); add(t,n+2+i+m,0);
        for(int x,j=1;j<=T;j++){
   
            scanf("%d",&x);
            add(n+2+i,x,inf);
            add(x,n+2+i,0);
            add(x,n+2+i+m,inf);
            add(n+2+i+m,x,0);
        }
    }
    int maxflow=0,flow=0;
    while(bfs()) 
        while(flow=dinic(s,0x3f3f3f3f)) maxflow+=flow;
    printf("%d\n",tot-maxflow);
    return 0;
}

最小费用最大流
dinic算法将第一次的bfs改成是spfa

就可以表示该点在最短路上（应该很好理解，和上面的dep[d]==dep[u]+1类似），那我们在增广时就可以走这条边。所以只要把dfs时的条件略作修改即可。

然后与dinic一样，跑dfs进行增广，同时累加最大流，最小费用，同时正向边减流，反向边加流。