最大流

FF方法(最大流算法的本质)：

对网络流为0的图找增广再在残量网络里找增广(一直下去，直到无法增广) 各路算法都是在写怎么增广(找增广路) EK算法： bfs增广，复杂度太高，一般不用

sap

时间复杂度 O(n^3) 【每个点访问了一次；每个点也都可能进入每一层；每个点都要遍历一遍其他的点，看是否有边】【所以是 n(点) * n（层） * n（点）】

网络流一般为稠密图(指边稠密) 网络流的增广=增流量

流不了然后将那一个的点提层提一级之后，其实走的是残留网络里的增广路

本质：以动态最短路【因为要提层，所以是动态的】的方式枚举所有的路(S==>T)，即所有的动态最短路加起来，就是所有可行流（即所有从S到T的路）在枚举过程中，同时也遍历了可行流，最后回溯求出了最大流

代码：

int s,t;  //s为源 //t为汇 
int d[N],cntd[N]; //d[i]=x表示i点在第x层 //cntd[i]表示i层的点数 
int dfs(int x,int flow){ //x表示点x  //flow表示流入x的流量 //dfs求的是从x可以流出的流量 即x流向终点的流量
	if(x==t) return flow;  //如果x==t，返回流量 
	int sum=0; //sum为从x流出的流量 
	for(int i=1;i<=n;++i){ //遍历点 
		if(e[x][i]&&d[x]==d[i]+1){ //i为x的下一层 
			int tmp=dfs(i,min(e[x][i],flow-sum)); //tmp表示通过此边 x->i 的流量 【通过此边从x流向i的流量】 //tmp表示通过这条边流向终点地流量 
			e[x][i]-=tmp;
			e[i][x]+=tmp; //加反边
			sum+=tmp;
			if(sum==flow) return sum; //流入的水都流出了，就return 
		}
	}
	if(d[s]>=n) return sum; //d[s]>=n表示有断层 
	cntd[d[x]]--;
	if(cntd[x]==0) d[s]=n; //cntd[x]==0说明d[x]层断层了，所以打一个d[s]=n的标记【表示断层的含义】,即相当于fg的作用
						   //s最多只到n-1层【t始终在0层】,所以n为d的不可能取值 
	d[x]++;
	cntd[d[x]]++;
	return sum; 
}

Dinic

O(n^n^n)【实际上，它的复杂度比spa优秀一点】求一次最短路，求一次dfs(即求增广）如此往复，直至不能增广

每一次dfs都是增广一大把（即找到一大把可行流）

从源点开始做一次bfs（求定标）（找s==>t的最短路，求出来的定标就是到s的最短路）一次bfs可以更新所有定标

最大流不可能同时卡spa和Dinic 前向星处理重边问题很优秀奇数^1==偶数（==奇数-1）偶数^1==奇数（==偶数+1）

int d[N];
queue<int>q;
bool bfs(int s,int t){ //bfs在残量网络里跑最短路，搜顶标
	memset(d,0,sizeof d);
	while(!q.empty()) q.pop(); 
	d[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		if(u==t) return 1;  //搜到了终点，return 
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].a;
			if( d[v]==0 && e[i].len ){  //d==0可以表示还没访问过 
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
int dfs(int x,int flow,int t){  //dfs求的是从x可以流向终点的流量
	if(x==t) return flow;
	int sum=0;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].a;
		if(d[x]+1==d[y]&&e[i].len){
			int tmp=dfs(y,min(flow-sum,e[i].len),t);
			e[i].len-=tmp;
			e[i^1].len+=tmp;  //加反边
			sum+=tmp;
			if(sum==flow) return flow;
		}
	}
	return sum;
}
int main(){
	int ans=0;
	while(bfs(s,t)){ //bfs搜顶标 
		ans+=dfs(s,INF,t);
	}
	return 0; 
}

spa和Dinic： spa：从i点到t的最短路，即从t开始的最短路 Dinic：从s开始的最短路，即从i到s的最短路

最小费用最大流（保证流最大的情况下费用最小）

w：单位流量费用

退流时要还钱则会有原先边权的相反数即 spfa

求最大流时： dfs优先增广费用小的（最短路）全部增广完时，求出的最大流就是最小费用

int cnt,head[N];
struct node{
	int a,cap,next,ct,fw;  //cap表示管道容量，ct(cost)表示单位流量费用，fw(flow)表示流量 
}e[M<<1];  //ct的作用就是找最短路时和计算答案，其他地方用不着 
void add(int x,int y,int cap,int ct) {
	e[cnt].a=y;
	e[cnt].cap=cap;
	e[cnt].ct=ct;
	e[cnt].fw=0;
	e[cnt].next=head[x];
	head[x]=cnt++
}

int dis[N],pre[N]; //pre[x]=i表示x前驱的那条边【即前驱边】 在前向星中的标号为i 
//设x的前驱为u,则pre记录的是u->x此边，且它记录的是最小费用的边 
bool vis[N];  //是否在队列中 
bool spfa(int s,int t){
	queue<int>q;
	for(int i=0;i<n;++i){
		dis[i]=INF;vis[i]=0;pre[i]=-1;
	}
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=e[i].next){   
			int v=e[i].a;
			if( dis[u]+e[i].ct<dis[v] && e[i].cap>e[i].fw ){  //花费地更少 且 还有容量可以流水，就更新 
				dis[v]=dis[u]+e[i].ct;
				pre[v]=i;  //记录前驱边 
				if(vis[v]==0){  //如果它不在队列，就让它入队
					q.push(v); 
				}
			}
		}
	}
	if(pre[t]==-1) return 0;  //表示求最短路时，没有更新到t，则无可行流了 
	return 1; 
}

//返回的是最大流，ct存的是最小费用 
int solve(int s,int t,int& ct){  //求的是s到t的最大流 或者 s可以流出的流量【最大的】 
	int fw=0;
	cost=0;
	while(spfa){  //每次用最短路找一条费用最小的可行流 
		int minx=INF; //minx是spfa找出可行流的最大流，即残量网络可行流中的最小管道容量
		for(int i=pre[t];i!=-1;i=pre[e[i^1].a]){  //反向边的终点就是原边的起点 或者说 反向边的终点就是原点的前驱 
			minx=min(minx,e[i].cap-e[i].fw);
		}
		for(int i=pre[t];i!=-1;i=pre[e[i^1].a]){
			e[i].fw+=minx;
			e[i^1].fw-=minx;
			ct+=e[i].ct*minx; 
		}
		fw+=minx; 
	}
	return fw;
} 

int main(){
	memset(e,-1,sizeof e);
	memset(head,-1,sizeof head);
	add(a,b,c,d);add(b,a,0,-c);
	sovle(s,t,ans);
	return 0;	
}

网络流

相关概念

最大流

FF方法(最大流算法的本质)：

sap

Dinic

最小费用最大流（保证流最大的情况下费用最小）