费用流1
概述
费用流,也叫作最小费用最大流,是指在普通的网络流图中,每条边的流量都有一个单价,求出一组可行解,使得在满足它是最大流的情况下,总的费用最小。
做法一般都是简单地SPFA(也就是和EK算法类似),时间复杂度比较高,所以一般规模都挺小的。 找到一条从源点到汇点的路径,使得这条路径的单价和最小。换句话说以流量的单价作为边权值跑最短路,这边推荐使用SPFA求最短路,如果有负环的话要考虑使用消圈法。
最大流最小费用
有n个点,接下来 m 行,每行三个整数 u,v,c,w,表示从点 u 到点 v 存在一条有向边,容量为 c,费用为 w。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e3+10,M=1e5+10;
int n,m,S,T;
int head[N],idx;
int q[N],d[N],cur[N];
int pre[N],incf[N];
bool st[N];
struct Edge{
int next,to,f,w;
}edge[M];
void add(int a,int b,int c,int d)
{
edge[idx]=(Edge){head[a],b,c,d},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0,-d},head[b]=idx++;
}
bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
memset(st,false,sizeof st);
q[0] = S, d[S] = 0, incf[S] = inf;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = head[t]; ~i; i =edge[i].next)
{
int ver = edge[i].to;
if (edge[i].f && d[ver] > d[t] + edge[i].w)
{
d[ver] = d[t] + edge[i].w;
pre[ver] = i;
incf[ver] = min(edge[i].f, incf[t]);
if (!st[ver])
{
q[tt ++ ] = ver;
if (tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
void EK(int& flow, int& cost)
{
flow = cost = 0;
while (spfa())
{
int t = incf[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = edge[pre[i] ^ 1].to)
{
edge[pre[i]].f -= t;
edge[pre[i]^1].f += t;
}
}
}
int main()
{
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(head, -1, sizeof head);
while (m -- )
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
add(a,b,c,d);
}
int flow, cost;
EK(flow, cost);
printf("%d %d\n", flow, cost);
return 0;
}
最大流最大费用
没有大的变化注意一下把每次求最短路换成求最长路即可。
bool spfa()
{
int hh=0,tt=1;
memset(st,false,sizeof st);
memset(d,0xcf,sizeof d);
memset(incf,0,sizeof incf);
q[0]=S,d[S]=0,incf[S]=inf;
while(hh!=tt)
{
int t=q[hh++];
if(hh==N) hh=0;
st[t]=false;
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(edge[i].f&&d[ver]<d[t]+edge[i].w)
{
d[ver]=d[t]+edge[i].w;
pre[ver]=i;
incf[ver]=min(edge[i].f,incf[t]);
if(!st[ver])
{
q[tt++]=ver;
if(tt==N) tt=0;
st[ver]=true;
}
}
}
}
return incf[T]>0;
}