网络流-费用流

定义

给定一个有 \(n\) 个点 \(m\) 条边的网络，每条边有一个容量限制 \(C_{x\to y}\) 和一个使用的代价 \(w_{x\to y}\)。当边 \(x\to y\) 使用的流量为 \(f_{x\to y}\) 时，其花费的代价为 \(w_{x\to y}\times f_{x\to y}\)。这个网络中总共代价最少的最大流被称为最小费用最大流，总共代价最多的最大流被称为最大费用最大流。

注意：费用流是建立在最大流的基础上的，让流量的大小是第一关键字。

求解

因为最大流是一样的，所以依然可以套用 Dinic 的思路。因为 Dinic 的增广路长度是可以贪心的寻找的，所以只要每一次增广路的费用最小，那么就可以让费用最小。所以我们可以将将代价看作边权，把原本的 bfs 换成 spfa 找最短路。

如果需要求解费用最大最大流，那么只需要将所有的边取反，再跑一次费用最小最大流就可以了。

实现

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=1e6,inf=0x3f3f3f3f3f3f3f3f;
struct node{int x,v,w,id;};
vector<node> v[N];
void add(int x,int y,int val,int w){
    int sti=v[x].size(),edi=v[y].size();
    v[x].push_back({y,val,w,edi});
    v[y].push_back({x,0,-w,sti});
}
int n,m,s,t,dep[N],p[N],sum;
bool vis[N];
bool bfs(){
	memset(dep,0x3f,sizeof(dep));
	memset(p,0,sizeof(p));
    memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(s);
	vis[s]=1,dep[s]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		for(node i:v[x]){
			if(i.v&&dep[x]+i.w<dep[i.x]){
				dep[i.x]=dep[x]+i.w;
				if(!vis[i.x]){
                    vis[i.x]=1;
                    q.push(i.x);
                }
			}
		}
	}
	return dep[t]!=inf;
}
int dfs(int x,int flow){
    if(x==t){
        return flow;
    }
    vis[x]=1;
    for(int i=p[x];i<v[x].size();i++){
        p[x]=i;
        int to=v[x][i].x,len=v[x][i].v;
        if(!vis[to]&&dep[x]+v[x][i].w==dep[to]&&len){
            int t=dfs(to,min(len,flow));
            if(t){
                v[x][i].v-=t;
                v[to][v[x][i].id].v+=t;
                sum+=t*v[x][i].w;
                return t;
            }
            else{
                dep[to]=-1;
            }
        }
    }
    vis[x]=0;
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs()){
        ans+=dfs(s,inf);
    }
    return ans;
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=1,x,y,val,w;i<=m;i++){
        cin>>x>>y>>val>>w;
        add(x,y,val,w);
    }
    cout<<dinic()<<' '<<sum<<'\n';
    return 0;
}