P3381 【模板】最小费用最大流题解

前置知识：

简要题意：

给定网络图，求图的最大流，以及流量为最大流时的最小费用。

现在假设你们看了那篇网络流博客之后，所有人都会了 \(\text{EK , FF , dinic}\) 算法。

然后我们来介绍一个新的思想。

假设我们从最短路的角度出发，仍然采用之前那个 “反悔” 思想，那么此时 可以用 \(\text{SPFA}\) 来实现每次增广，增广的时候，你会发现原来代码里的 found 函数用来查询反向边。但是这次我们不用了，我们再建边 \(u \rightarrow v\) 的时候，就建立一个 \(\text{rev}\)，表示当前边在另外一个顶点里的编号。

比方说 \(3 \rightarrow 5\) 在 \(3\) 的边中是第 \(2\) 条，那么 \(5\) 对于这条边的 \(\text{rev}=2\)，便于我们迅速查找反向边。

然后考虑如何在最大流的基础上求出最小费用？我们沿袭 \(\text{SPFA}\) 中的 \(\text{dis}\)，这是用来求最短路的，那么我们正好用 \(\text{dis}\) 把费用（即最短路中的边权）记录一下，正好可以达到这个效果。

所以说 \(\text{SPFA}\) 在某种意义上并没有死，因为它的常数出奇地小或许能卡过一些题目（比方说这道）。

当然了，如果真想用 \(\text{dijkstra}\) ，那么要用到 Johnson 全源最短路中 \(\text{Johnson}\) 提出的，“构造上帝节点，依据最短路将边权构造为非负” 的思想。那样的话复杂度就是 \(O(nm \log n)\) 了。

时间复杂度：\(O(n^2m)\).（显然 \(\text{SPFA}\) 一次是 \(n^2\) 的）

实际得分：\(100pts\).（因为实际上根本跑不满的，不可能每次都会到上限）

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

const int N=5e4+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}

	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

struct node {

	int to,flow,rev,cost; //to 是边终点 , flow 是流量 , rev 是反向边编号 , cost 是费用

} ;

vector<node> G[N];

int dis[N],pre1[N],pre2[N]; //pre1[i] 是正常网络流的前驱 pre2[i] 是前驱的边编号 , 类似于 rev , 有利于最后的反悔操作

int flow[N],n,m,s,t,ans;

bool vis[N]; int maxf;

inline bool SPFA() {

	fill(dis+1,dis+1+n,2e9);

	memset(vis,0,sizeof(vis));

	queue<int> q; dis[s]=0; vis[s]=1; flow[s]=2e9;

	q.push(s);

	while(!q.empty()) {

		int u=q.front(); q.pop(); vis[u]=0;

//		printf("%d\n",u);

		for(int i=0;i<G[u].size();i++) {

			node t=G[u][i]; int v=t.to; //向外增广

			if(t.flow>0 && t.cost+dis[u]<dis[v]) {

				dis[v]=dis[u]+t.cost;

				pre1[v]=u; pre2[v]=i;

				flow[v]=min(flow[u],t.flow); //记录答案

				if(!vis[v]) vis[v]=1,q.push(v);

			}

		}

	}

//	for(int i=1;i<=n;i++) printf("%d ",dis[i]); puts("");

//	for(int i=1;i<=n;i++) printf("%d ",flow[i]); puts("");

//	for(int i=1;i<=n;i++) printf("%d ",pre1[i]); puts("");

//	for(int i=1;i<=n;i++) printf("%d ",pre2[i]); puts("");

	return dis[t]!=(2e9);

}

inline void update() {

	int k=t; while(k-s){ //不到源点就继续反悔

		int p=pre1[k],q=pre2[k];

		G[p][q].flow-=flow[t];

		G[k][G[p][q].rev].flow+=flow[t]; //套路

		k=p;

	} maxf+=flow[t];

	ans+=dis[t]*flow[t]; //费用更新

}

inline void dinic() {

	while(SPFA()) update();

}

int main(){

	n=read(),m=read(),s=read(),t=read();

	while(m--) {

		int u=read(),v=read(),w=read(),f=read();

		G[u].push_back(node{v,w,G[v].size(),f});

		G[v].push_back(node{u,0,G[u].size()-1,-f});

	} dinic();

	printf("%d %d\n",maxf,ans);

	return 0;

}

巴特西

P3381 【模板】最小费用最大流题解

最新文章

热门文章

巴特西

P3381 【模板】最小费用最大流 题解

最新文章

热门文章

P3381 【模板】最小费用最大流题解