网络流简介

网络流在 OI 中是显得尤为重要的,网络流是一种将“信息”类比水流流动,套用网络流算法解决问题的一种策略,用于求解网络上的最优化问题。

网络

网络流常见问题

  • 最大流 :求一张图中从源点流向汇点的最大流量(可以有很多条路到达汇点)

  • 最小(大)费用最大流 :每条边都有一个费用,代表单位流量流过这条边的开销。我们要在求出最大流的同时,要求花费的费用最小

  • 最小割 :割其实就是删边的意思,当然最小割就是割掉X条边来让 ST 不互通。我们要求 X 条边加起来的流量综合最小

  • 最大权闭合子图

  • 最大密度子图

  • 二分图最小点权覆盖集

  • 二分图最大点权独立集

  • ……

最大流

概述:我们有一张图,要求从源点( S )流向汇点( T )的最大流量(可以有很多条路到达汇点)

比如把源点比作工厂的话,问题就是求从工厂最大可以发出多少货物,是不至于超过道路的容量限制

分类

这里主要介绍基于增广路方法的算法,因为比较经典好用

增广路方法

思想:不断求解增广路,当图中不存在增广路时就达到了最大流,因此增广路算法的效率取决于寻找增广路的方式

具体操作:从源点 S 开始不断向外广搜,通过权值大于 0 的边,直到找到汇点 T 为止,这条 路径即为一条增广路,找到该路径上边权最小的边,记为 min ,然后最大流加 min , 同时把该路径上的每一条边的边权减去 min ,直到找不到一条增广路为止最大流即加和结果

效率排名 ISAP>Dinic>EK≈FF ,所以学了 EK 就不学 FF 了,但是 ISAP 和 Dinic 都要学

相关概念

残量网络

就是是增广之后的网络

增广路

4->3 肯定可以先从流量为20的边走,至此这条边不能再走了总的流量为 20 。然后还可以选其他的路走(增广路):

  • 4->2->3 这条增广路的总流量为 20(到 2 的时候是 30 ,但是到 3 最多走 20 )
  • 4->2->1->3 就可以让总量保持 30

综上我们的最大流应该是 20+30=50

反向边

在做增广路时可能会阻塞后面的增广路,或者说,做增广路本来是有个顺序才能找完最大流的。但我们是任意找的,为了修正,就每次将流量加在了反向弧上,让后面的流能够进行自我调整。事实证明增广是建立反向边可以实现程序的反悔从而避免错误

建反向边时:反向和存入的边方向相反,容量初始设为 0 ,费用取相反数。每次找到一个增广路将边减少delta的同时也要将反向边加上 delta ,费用仍然是相反

Edmond-Karp动能算法(EK算法)

参考博客 虽然解决问题时不会再用这个算法但是其他算法都是基于这个增广的思想,博客讲的很清楚

方法:每次都是 BFS 直接找增广路+进行增广

过程:其实就是每次贪心找增广路,但是因为 BFS 是盲目的找增广路,可能会导致前面找的增广路影响了后面找增广路所以借助反向边不断纠正错误达到最优解

时间复杂度:O(VE2)

模板

模板题:有 n 个水管,有 m 个点,源点为 1 ,汇点为 m ,求汇点 T 单位时间的最大水流量,当然这题有个小坑,就是输入会重复,如果 1->2 40 代表从 1 流向 2 有 40 流量,那可能会有多次 1->2 401->2 30 之类的,要累加成 1->2 70

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
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;

int n,m;
int c[N][N];//记录i到j的剩余流量
int p[N];//p[i]记录流向i点的前驱节点
int v[N];//记录在一条增广路中,流到i点时,此刻增广路上残余量的最小值,直到i == m时就是整条增广路上的残余量最小值


int min(int a, int b){
return a <= b ? a : b;
}

void EK(){
//从1出发,不断找可以到达m的增广路
int ans = 0;
while(true){
//EK算法的核心是通过bfs不断查找增广路,同时建立反向弧
//每次循环都要对v数组和p数组进行清空,因为是意图查找一条新的增广路了
memset(p, 0, sizeof(p));
memset(v, 0, sizeof(v));
queue<int> q;
q.push(1);
v[1] = INF;
//每次只找一条增广路,同时修改c[i][j]的值
while(!q.empty()){
int f = q.front();
q.pop();
for(int i = 1; i <= m; i++){
if(v[i] == 0 && c[f][i] > 0){//v[i]原本是记录增广路实时的残量最小值,v[i]==0代表这个点还没有走过,且从p到i的残量大于0说明通路
v[i] = min(v[f], c[f][i]);//实时更新v[i]的值,v[f]存储1条增广路中i点前所有水管残量的最小值,v[i]为该条增广路到i点为止,路径上的最小残量
p[i] = f;//p[i]实时保存i点的前驱节点,这样就当i==m时整条增广路就被记录下来
q.push(i);//将i点入队
}
}
}
if(v[m] == 0) break;//如果v[m]==0则代表找不到增广路了(中途出现了c[i][j]==0的情况)
ans += v[m];
int temp = m;
while(p[temp] != 0){//类似并查集的查操作,不断查上一个元素且将剩余残量减去最小残联,反向弧增加最小残量
c[p[temp]][temp] -= v[m];
c[temp][p[temp]] += v[m];
temp = p[temp];
}
}
printf("%d\n", ans);
}

signed main(){
while(scanf("%d%d", &n, &m) != EOF){
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; i++){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
c[x][y] += z;//初始时,从x流向y的剩余流量就是输入的值
}
EK();
}
return 0;
}

以下的的所有算法模板都是为了解决这道题,区别在于能够解决的变量范围。最大流模板题:给定n个点,m条有向边,给定每条边的容量,求从点 s 到点 t 的最大流

Dinic算法

方法:每次都是 BFS 将图分层 + DFS 找最短增广路 + 进行增广

过程:在 EK 算法基础上选增广路更明智一些,每次增广前先用 BFS 将图分层,设源点的层数为 0 那么一个点的数便是它离源点最近的距离。通过分层可是实现两个事情:

  • 如果不存在到汇点的增广路(即汇点的层数不存在)我们即可停止增广
  • 确保我们找到的增广路是最短的

然后在我们 DFS 的找增广路的时候都只找比当前层数多 1 的点进行增广(这样就可以确保我们找到的增广路是最短的)

时间复杂度:O(V2E) ,优化后效率会再高一点点

优化

  • 多路增广 :每次找到一条增广路的时候,如果残余流量没有用完怎么办呢?我们可以利用残余部分流量,再找出一条增广路。这样就可以在一次 DFS 中找出多条增广路,大大提高了算法的效率

  • 当前弧优化 :如果一条边已经被增广过,那么它就没有可能被增广第二次。那么,我们下一次进行增广的时候,就可以不必再走那些已经被增广过的边

  • 炸点优化:如果当前点不能增广最大流了,就把他“炸掉”

模板

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//Dinic+多路优化+当前弧优化+炸点优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 120005;
const ll inf = 0x3f3f3f3f;

ll s,t, cnt; //源点和汇点,cnt:边的编号
ll head[N], dis[N], cur[N]; //head:u点对应当前最后一条边编号,dis:点层数

struct node{//链式前向星
ll v, f;//边汇点 边容量
ll next;//u点前一条边编号
} edge[1000005];//边集

inline void init() {//初始化
cnt = 0;
memset(head,-1,sizeof head);
}

inline void add(ll u,ll v,ll f) { //边集加边
edge[cnt].v = v;
edge[cnt].f = f;
edge[cnt].next = head[u];
head[u] = cnt++;
}

inline ll bfs(ll ds, ll t) { //bfs建立分层图
memset(dis, -1, sizeof(dis)); //初始化层数
dis[ds] = 0; //源点层数设为0
queue<ll>q; //bfs队列
q.push(s) ;
while( !q.empty() ) {
ll u = q.front();
q.pop();
if(u == t) return 1; //优化:找到即返回
for(ll i = head[u] ; ~i ; i = edge[i].next) { //遍历u点的边集
ll v = edge[i].v ; //取出边汇点
if( dis[v] == -1 && edge[i].f ) { //边未设层数且有容量
dis[v] = dis[u] + 1 ; //v层数为u层数+1
q.push(v) ;
if(v == t) break;
}
}
}
return dis[t] > 0;
}

inline ll dfs(ll ds, ll t, ll min1) {//dfs寻找增广路
if( ds == t )//到达汇点直接返回
return min1 ;
ll flow,ans = 0 ;
for(ll i = cur[ds] ; ~i; i = edge[i].next) { //遍历ds的边集
//head改为cur:当前弧优化
ll v = edge[i].v ;//取出边汇点
cur[ds] = i;
if( dis[v] == dis[ds] + 1 && edge[i].f ) {
// 满足分层图且有容量
if(flow = dfs(v, t, min(min1 - ans, edge[i].f) ) ) {
//向下继续增广,扩大最大流量
edge[i].f -= flow ;//正向减流
edge[i ^ 1].f += flow ;//反向增流
ans += flow ; //总增流
if(min1==ans)//若完全增流,结束搜索
break;
}
}
}
if(!ans )//若无流量,炸点优化
dis[ds] = -1 ;
return ans;
}

inline ll dinic() {//返还最大流
ll ans = 0, x;
while(bfs(s, t)) {
memcpy(cur, head, sizeof(head)); //当前弧优化
while(x = dfs(s, t, inf))
ans += x;
//printf("%d\n",x);
}
return ans;
}
inline void addedge(ll u, ll v, ll f) {
add(u, v, f);
add(v, u, 0);
}

ll n,m;//n个点m条边

signed main()
{
init();
//cin>>n>>m>>s>>t ;
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
ll u,v,w;
for(ll i=1;i<=m;i++){
cin>>u>>v>>w;
addedge(u,v,w);
}
//cout<<dinic()<<endl;
printf("%lld\n",dinic());

/*
//目前还不知道这是那道题用得上的
for(ll i=1;i<=m;++i) add(s,i,1),add(i,s,0);
for(ll i=m+1;i<=n;++i) add(i,t,1),add(t,i,0);
while(~scanf("%d%d",&x,&y),~x,~y){
add(x,y,1);
add(y,x,0);
}

ll sum = dinic();
if(!sum) puts("No Solution!");
else{
//遍历所有边
printf("%d\n",sum);
for(ll i=0;i<=cnt;i+=2){
if(edge[i^1].v!=s&&edge[i].v!=t&&edge[i^1].f!=0)
printf("%d %d\n",edge[i^1].v,edge[i].v);
}

}*/
system("pause");
return 0;
}

ISAP算法

引入:其实是 SAP 算法的加强版。都是在 Dinic 算法基础上进一步改进的,每次 DFS 找最短路是没法进一步改进的,但是可以不用每次都 BFS 重新分层,我们可以每次 DFS 找完增广路后直接在之前的 BFS 分层图的基础上改进深度

方法:先一次 BFS 将图分层,每次都 DFS 找最短路增广路+进行增广+分层图的距离调整

过程:先从源点 T 到汇点 S 跑一次 BFS 标记深度进行分层,然后从 S 到 T 跑 DFS(类似 dinic )找增广路进行增广,只是当一个点跑完后,如果从上一个点传过来的 flow 比该点的 used 大(对于该点当前的深度来说该点在该点以后的路上已经废了)则把它的深度加1, 如果出现断层(某个深度没有点)结束算法,吐过没有结束就继续循环 DFS 找增广路

时间复杂度:O(V2E),优化后复杂度会降一大截,非常可观基本没有卡的住的题

优化

  • gap 优化:ISAP 进行逆向的分层,DFS 增广时需要正向进行,且满足 dep[u]=dep[v] + 1gap 优化记录每一深度点的 数量,也就是说如果出现了断层(即gap[i]==0),也就是说在某一深度的层级中不存在节点,那么就不会再出现可行流直接结束算法

gap 优化是 ISAP 最强的优化,没有 gap 优化的 ISAP 都是废物

  • 当前弧优化:和 dinic 中相同,如果一条边已经被增广过,那么它就没有可能被增广第二次。那么,我们下一次进行增 广的时候,就可以不必再走那些已经被增广过的边

模板

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//ISAP+GAP优化+当前弧优化
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const ll max_node=1205,max_edge=120005;//最大顶点数和最大边

struct Edge{
ll from, to, f;
};

ll n, m, s, t, ct=1;
ll Hed[max_node], Nex[2*max_edge], Cur[max_node], Dep[max_node], Num[max_node], Pre[max_node];
Edge E[2*max_edge];

void Add(ll &a, ll &b, ll &f){
E[++ct].from=a, E[ct].to=b, E[ct].f=f, Nex[ct]=Hed[a], Hed[a]=ct;
E[++ct].from=b, E[ct].to=a, E[ct].f=0, Nex[ct]=Hed[b], Hed[b]=ct;
}

inline void BFS(){
queue<ll> Q;
memset(Dep, 0, sizeof Dep);
Dep[t] = 1; Q.push(t);
ll k;
while(!Q.empty()){
k = Q.front(); Q.pop();
Num[Dep[k]]++;
for(ll i=Hed[k]; i; i=Nex[i]){
if(E[i^1].f && !Dep[E[i].to]){
Dep[E[i].to] = Dep[k]+1;
Q.push(E[i].to);
}
}
}
}

inline ll Agument(){
ll k = t, flow = INF;
while(k != s){
if(E[Pre[k]].f < flow) flow = E[Pre[k]].f;
k = E[Pre[k]].from;
}
k = t;
while(k != s){
E[Pre[k]].f -= flow;
E[Pre[k]^1].f += flow;
k = E[Pre[k]].from;
}
return flow;
}

inline ll ISAP(ll maxdep){
ll flow = 0, k = s, mindep;
BFS();
memcpy(Cur, Hed, sizeof Hed);
bool can;
while(Dep[s] <= maxdep){
if(k == t){
flow += Agument();
k = s;
}
can = 0;
for(ll i=Cur[k]; i; i=Nex[i]){
if(E[i].f && Dep[E[i].to]+1==Dep[k]){
can = 1;
Pre[E[i].to] = i;
Cur[k] = i;
k = E[i].to;
break;
}
}
if(!can){
mindep = n+1;
for(ll i=Hed[k]; i; i=Nex[i])
if(Dep[E[i].to]<mindep && E[i].f)
mindep = Dep[E[i].to];

if(!--Num[Dep[k]]) break;
Num[Dep[k]=mindep+1]++;
Cur[k] = Hed[k];
if(k != s) k = E[Pre[k]].from;
}
}
return flow;
}

signed main(){
scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
ll u, v, c;
for(ll i=1; i<=m; ++i){
scanf("%lld%lld%lld", &u, &v, &c);
Add(u, v, c);
}
printf("%lld\n", ISAP(n));//传入顶点数(最大深度)
//system("pause");
return 0;
}

预流推进算法

思想:该方法在求解过程中忽略流守恒性,并每次对一个结点更新信息,以求解最大流

相关概念

  • [ ] 现在还没理解待更新,就记一个最高效率的算法有时候要用到

HLLP算法(最高标号预流推进算法)

引入:就之前增广路的模板题讲,那道题的数据范围很大,顶点数最大为 1200 个,边最大为 120000个 ,限制时间为 1500ms ,即使优化了 O(V2E) 的算法( Dinic 和 ISAP )都会被卡 TLE

参考博客 具体讲解看看这个博客,凡人就学会套用就好了

时间复杂度:O(V2√E)

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
//hlpp优化版(最高标签预流推进算法),上限紧但是高效时间复杂度O(V^2sqrt(E))
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll max_node = 1500;
const ll max_edge = 250000;
const ll inf = 0x3f3f3f3f;
ll n, m, s, t, N;
struct Edge {
ll y, prev, nxt;
ll cap;
} e[max_edge];
ll elast[max_node], ecnt = 1;
ll h[max_node], gap[max_node], cur[max_node];
ll ex[max_node];//暂时存储源点到非源点的最大流,结果就是ex[t]
ll pre[max_node], lst[max_node], tp;

//内联函数加快函数运行速度
inline void ins(ll u, ll h) {
tp = tp < h ? h : tp;
pre[u] = lst[h];
lst[h] = u;
}

inline void take(ll& u, ll h) {
u = lst[h];
lst[h] = pre[u];
pre[u] = 0;
}

inline void Build(ll x, ll y, ll z) {
e[++ecnt] = { y, elast[x], 0, z };
elast[x] = ecnt;
e[++ecnt] = { x, elast[y], 0, 0 };
elast[y] = ecnt;
}

inline void bfs() {
for (register ll i = 1; i <= N; ++i) {//register加开读取
h[i] = N + 1;
gap[i] = 0;
}
h[t] = 0;
static ll q[max_node];
ll hd = 0, tl = 0;
q[tl++] = t;
while (hd != tl) {
ll u = q[hd++];
for (ll i = elast[u]; i; i = e[i].prev) {
ll v = e[i].y;
if (h[v] > h[u] + 1) {
h[v] = h[u] + 1;
q[tl++] = v;
}
}
}
}

inline void push_flow(ll u) {//预留推进函数
for (ll& i = cur[u]; i; i = e[i].nxt) {
ll v = e[i].y;
if (e[i].cap && h[u] == h[v] + 1) {
ll f = min(e[i].cap, ex[u]);
if (!ex[v] && v != s && v != t)
ins(v, h[v]);
e[i].cap -= f;
e[i ^ 1].cap += f;
ex[u] -= f;
ex[v] += f;
if (!ex[u])
break;
}
}
}

inline void relabel(ll u) {
h[u] = N + 1;
for (ll i = elast[u]; i; i = e[i].prev) {
if (e[i].cap && h[u] > h[e[i].y] + 1)
h[u] = h[e[i].y] + 1;
}
}

void hlpp() {
bfs();
if (h[s] == N + 1)
return;
h[s] = N;
for (ll i = 1; i <= N; ++i) {
if (h[i] < N)
gap[h[i]]++;
for (ll j = elast[i]; j; j = e[j].prev) {
if (h[i] == h[e[j].y] + 1) {
e[j].nxt = cur[i];
cur[i] = j;
}
}
}
for (ll i = elast[s]; i; i = e[i].prev) {
ll v = e[i].y;
if (e[i].cap && h[v] <= N) {
ex[v] += e[i].cap;
ex[s] -= e[i].cap;
e[i ^ 1].cap = e[i].cap;
e[i].cap = 0;
if (v != t)
ins(v, h[v]);
}
}
while (tp) {
ll u;
take(u, tp);
if (tp != h[u]) {
while (tp && !lst[tp]) tp--;
continue;
}
push_flow(u);
if (ex[u]) {
if (!--gap[h[u]]) {
for (register ll i = 1; i <= N; ++i)
if (h[i] > h[u] && h[i] <= N) {
gap[h[i]] = 0;
h[i] = N + 1;
}
}
relabel(u);
for (ll i = elast[u]; i; i = e[i].prev) {
ll v = e[i].y;
if (e[i].cap && h[v] + 1 == h[u]) {
e[i].nxt = cur[u];
cur[u] = i;
}
if (e[i ^ 1].cap && h[v] == h[u] + 1) {
e[i ^ 1].nxt = cur[v];
cur[v] = i ^ 1;
}
}
if (h[u] <= N)
gap[h[u]]++, ins(u, h[u]);
}
while (tp && !lst[tp]) --tp;
}
}

signed main() {
//cin >> n >> m >> s >> t;//存入点数,边数,源点,汇点
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
for (ll i =1; i<= m; ++i) {
ll x,y,z;
//cin >> x >> y >> z;
scanf("%lld%lld%lld",&x,&y,&z);
Build(x, y, z);
}
N=n;//给hlpp传递总的点数
hlpp();
//cout << ex[t];
printf("%lld\n",ex[t]);
//system("pause");
return 0;
}

总结比较

算法 时间复杂度 评价 建议
EK O(VE2) 根本不用 思想应该了解
Dinic O(V2E) 常用,上限松 必会推荐用
ISAP O(V2E) 高效,上限松 必会防卡
HLPP O(V2√E) 最高效,上限紧 必会没事别用

上限:表示该算法可能有的最高增长率

下限:表示该算法可能有的最低增长率

最小割

相关概念

最大流最小割定理

视频讲解 证明不理解没关系看看这个老师的视频讲解多体会

方法:从源点 S 开始 DFS ,每次走残量大于 0 的边找到所有 S 点集合的点,(根据定理直接套最大流板子就是最小割了)

用途:解决利益冲突情况下的利益最大化问题

求割边数量:只需要将每条边的容量变为 1 ,然后重新跑最大流模板即可

费用流

相关概念

MCMF算法

思想:在最大流的EK算法求解最大流的基础上,把用 BFS 求解任意增广路改为用 SPFA 求解单位费用之和最小的增广路即可

模板题:给定一个图,每条边有容量和费用,使用每条边的单位流量需要支付特定的费用。给定源点 1 和汇点 n ,求图的最大流和最大流需要支付的最小费用

模板

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//求最大费用最小流的板子
#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 5e3 + 5, M = 5e5 + 5;
const int inf = 0x3f3f3f3f;

int tot, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N];
ll ret;//记录最小费用费用
bool vis[N];

void init() {
tot = 1, ret = 0;
memset(lnk, -1, sizeof lnk);
}

void add(int u, int v, int w, int c) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}

void addedge(int u, int v, int w, int c) {
add(u, v, w, c), add(v, u, 0, -c);//加反向边
}

bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memcpy(cur, lnk, sizeof(lnk));
queue<int> q;
q.push(s), dis[s] = 0, vis[s] = 1;
while(!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for(int i = lnk[u]; ~i; i = nxt[i]) {
int v = ter[i];
if(cap[i] && dis[v] > dis[u] + cost[i]) {
dis[v] = dis[u] + cost[i];
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return dis[t] != inf;
}

ll dfs(int u, int t, int flow) {
if(u == t) return flow;
vis[u] = 1;
ll ans = 0;
for(int &i = cur[u]; ~i && ans < flow; i = nxt[i]) {
int v = ter[i];
cur[u] = i;
if(!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
ll x = dfs(v, t, min((ll)cap[i], flow - ans));
if(x) ret += x * cost[i], cap[i] -= x, cap[i ^ 1] += x, ans += x;
}
}
vis[u] = 0;
return ans;
}

ll mcmf(int s, int t) {
ll ans = 0;
while(spfa(s, t)) {
ll x;
while((x = dfs(s, t, inf))) ans += x;
}
return ans;//最大流量
}

signed main() {
int n, m, x, pp, mm, ff, nn, ss, s, t;
scanf("%d%d", &n,&m);//n个点m条边
init();
s=1,t=n;//源点和汇点

for(int i=1;i<=m;i++){
int x,y,z,c;
cin>>x>>y>>z>>c;//存入两个端点、容量和费用
addedge(x,y,z,c);
}
cout<<mcmf(s,t)<<" ";//输出最大流
printf("%lld\n",ret);//输出最小费用
/*for(int i = 1; i <= n; ++i) {
scanf("%d", &x);
addedge(s, i, x, 0);
addedge(i + n, t, x, 0);
}
scanf("%d%d%d%d%d", &pp, &mm, &ff, &nn, &ss);
for(int i = 1; i <= n; ++i) {
addedge(s, i + n, inf, pp);
if(i < n) addedge(i, i + 1, inf, 0);
if(i + mm <= n) addedge(i, i + mm + n, inf, ff);
if(i + nn <= n) addedge(i, i + nn + n, inf, ss);
}*/
//system("pause");
return 0;
}