洛谷P3381 最小费用最大流 题解

Problem

题目描述

如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。

输入输出格式

输入格式:

第一行包含四个正整数$N,M,S,T$,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数$u_i,v_i,w_i,f_i$,表示第i条有向边从$u_i$出发,到达$v_i$,边权为$w_i$(即该边最大流量为$w_i$),单位流量的费用为$f_i$。

输出格式:

一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。

输入输出样例

1
2
3
4
5
6
7
Input #1
4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5
1
2
Output #1
50 280

说明

时空限制:1000ms,128MB

最后两个点1200ms

数据规模:

对于30%的数据:$N<=10,M<=10$

对于70%的数据:$N<=1000,M<=1000$

对于100%的数据:$N<=5000,M<=50000$

样例说明:

如图,最优方案如下:

第一条流为4–>3,流量为$20$,费用为$3×20=60$。

第二条流为4–>2–>3,流量为$20$,费用为$(2+1)×20=60$。

第三条流为4–>2–>1–>3,流量为$10$,费用为$(2+9+5)×10=160$。

故最大流量为$50$,在此状况下最小费用为$60+60+160=280$。

故输出$50 280$。

Solution

网络流模板题。

要求在满足最大流情况下的最小费用,可以在最大流的代码上做一些修改。

原本的EK算法是每次BFS只找流量最大的路径路径,现在要求最小费用,可以先找费用最小的,而不是流量最大的。毕竟有路肯定先挑费用少的走嘛。在EK上套一个SPFA就可以了。

如何证明该算法的正确性?

首先要知道,每条流的顺序对最大流的数值不产生影响。那么,先找费用最小的流,可以保证在满足最大流的情况下,找到最小的费用。并且,也不用担心某条流会因为费用太大跑不进去(除非有其他费用更小的流满足了最大流),费用再大也没有∞大,肯定是可以的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;

const int MAXN = 5000 + 5;
const int MAXM = 100000 + 5;
struct node { int from, to, next, cost, pay; }edge[MAXM];
int head[MAXN], cnt = 1;
int n, m, start, End;
int s, t, v, c;
int inc, ans, mincost;
int last[MAXN], flow[MAXN], dis[MAXN];
bool Visit[MAXN];
queue<int> q;

void add(int a, int b, int v, int p)
{
edge[++cnt].cost = v; edge[cnt].pay = p;
edge[cnt].from = a; edge[cnt].to = b;
edge[cnt].next = head[a], head[a] = cnt;
}

int bfs()
{
for (int i = 0; i < MAXN; i++) dis[i] = INF;
memset(Visit, false, sizeof Visit);
memset(last, 0, sizeof last);
q.push(start); flow[start] = INF; dis[start] = 0; Visit[start] = true;
while (!q.empty())
{
int now = q.front(); q.pop(); Visit[now] = false;
for (int i = head[now]; i; i = edge[i].next)
{
int f = edge[i].to;
if (edge[i].cost && dis[f] > dis[now] + edge[i].pay) //首先需要有流量才能访问,之后满足费用较小
{
flow[f] = min(flow[now], edge[i].cost);
last[f] = i, dis[f] = dis[now] + edge[i].pay;
if (!Visit[f]) Visit[f] = true, q.push(f); //SPFA找最小费用
}
}
}
if (!last[End]) return 0;
return flow[End];
}

void upd(int k)
{
int now = End;
while (now != start)
{
int p = last[now];
edge[p].cost -= k; edge[p ^ 1].cost += k;
now = edge[p].from;
}
mincost += dis[End] * k;
}

void maxflow() { while (inc = bfs()) upd(inc), ans += inc; }

int main()
{
cin >> n >> m >> start >> End;
for (int i = 1; i <= m; i++)
{
cin >> s >> t >> v >> c;
add(s, t, v, c); add(t, s, 0, -c); //反向边是反悔用的,反向互逆的两条流流量抵消,费用抵消
}
maxflow();
cout << ans << ' ' << mincost << endl;
return 0;
}

可能开始会有点懵,配上图仔细想一会就能理解。

Data

评测请至洛谷P3381

LOJ参考数据这里找

注意:LOJ题目和本题略有不同。