( ext{一:Dinic最大流})
最坏复杂度 ({mathcal O(n^2m)}) 一般可以处理 (10^4) ~ (10^5) 的网络。
struct Edge {
int v, w, nxt;
} E[M * 2];
int head[N], tot = 1;//记得从1存边
inline void add(int u, int v, int w) {
E[++tot] = (Edge) { v, w, head[u] };
head[u] = tot;
}
int n, m, d[N], S, T;
//bfs找增广路
bool bfs() {
queue<int> q;
memset(d, 0, sizeof(int) * (n + 1));
d[S] = 1;
q.push(S);
while (q.size()) {
int u = q.front();
q.pop();
for (register int i = head[u]; i; i = E[i].nxt) {
if (E[i].w and d[E[i].v] == 0) {
d[E[i].v] = d[u] + 1;
if (E[i].v == T) {
return true;
}
q.push(E[i].v);
}
}
}
return false;
}
int Dinic(int u, int flow) {
if (u == T) {
return flow;
}
int k, rest = flow;
for (register int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (E[i].w and d[v] == d[u] + 1) {
k = Dinic(v, min(E[i].w, rest));
if (k == 0) {
d[v] = 0;
}
E[i].w -= k;
E[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
//主函数中
for (register int u, v, w, i = 1; i <= m; ++ i) {
cin >> u >> v >> w;
add(u, v, w);//建边
add(v, u, 0);//反悔的边，记得w赋为0
}
int maxflow = 0, flow = 0;
while (bfs())
while (flow = Dinic(S, INF))
maxflow += flow;
二：( ext{Dinic费用流})
复杂度不知道，(10^3) ~ (10^4) 应该能跑。
struct Edge {
int v, w, cost, nxt;
} E[M * 2];
int head[N], tot = 1;//同上
inline void add(int u, int v, int w, int cost) {
E[++tot] = (Edge) { v, w, cost, head[u] }; //多加一维费用
head[u] = tot;
}
bool vis[N];
int n, m, d[N], S, T, mincost;
inline bool spfa() {//SPFA找增广路，要求增广路费用最小
queue<int> q;
memset(d, 0x3f, sizeof(int)*(n+1));
memset(vis, 0, (n+1));
d[S] = 0;
vis[S] = 1;
q.push(S);
while (q.size()) {
int u = q.front(), v;
q.pop();
vis[u] = 0;
for (register int i = head[u]; i; i = E[i].nxt) {
v = E[i].v;
if (E[i].w and d[v] > d[u] + E[i].cost) {
d[v] = d[u] + E[i].cost;
if (vis[v]) continue;
q.push(v);
vis[v] = 1;
}
}
}
return d[T] != d[0];
}
int Dinic(int u, int flow) {
if (u == T) {
return flow;
}
vis[u] = 1;//别忘了vis
int k, rest = flow;
for (register int i = head[u]; i and rest; i = E[i].nxt) {
int v = E[i].v;
if ((!vis[v] or v == T) and E[i].w and d[u] + E[i].cost == d[v]) {//这里多了个限制条件。
k = Dinic(v, min(E[i].w, rest));
if (k == 0) {
d[v] = 0;
}
rest -= k;
E[i].w -= k;
E[i ^ 1].w += k;
mincost += E[i].cost * k;//累计贡献（费用）
}
}
return flow - rest;
}
//主函数
for (register int i = 1; i <= m; ++ i) {
int u, v, c, w;
cin >> u >> v >> w >> c;
add(u, v, w, c);
add(v, u, 0, -c);//反悔的边cost为负
}
int maxflow = 0, flow;
while (spfa()) {//与最大流略有不同。
vis[T] = 1;
while (vis[T]) {
memset(vis, 0, (n+1));
maxflow += Dinic(S, INF);
}
}
三：一些题目：
DAG最小路径覆盖
建拆点二分图，跑dinic(或匈牙利)，答案 = 点数 - 最大流(最大匹配数)。
重点在如何递归输出路径，看代码。
/*
拆点的时候要拆成i与i+n
最好不要拆成i<<1 and i<<1|1
否则会出现玄学错误
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 5000, M = 6007;
int n, m, s = 0, t = 3500;
int ver[M<<1], d[N<<1], edge[M<<1], nxt[M<<1], head[N<<1];
int pre[N<<1], succ[N<<1], tot = 1;
void addEdge(int u, int v, int w) {
ver[++tot] = v; edge[tot] = w; nxt[tot] = head[u]; head[u] = tot;
}
int bfs() {
queue<int> q;
memset(d, 0, sizeof d);
q.push(s); d[s] = 1;
while (q.size()) {
int v, u = q.front(); q.pop();
for (int i = head[u]; i; i = nxt[i]) {
if (edge[i] and !d[v = ver[i]]) {
d[v] = d[u] + 1;
if (v == t) return 1;
q.push(v);
}
}
}
return 0;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow, v;
for (int i = head[u]; i and rest; i = nxt[i]) {
if (edge[i] and d[v = ver[i]] == d[u] + 1) {
k = dinic(v, min(edge[i], rest));
if (!k) d[v] = 0;
rest -= k;
edge[i] -= k;
edge[i ^ 1] += k;
if (v != t and k and u != s) {//记录路径
succ[u] = v - n;
pre[v - n] = u;
}
}
}
return flow - rest;
}
int vis[N<<1];
void put(int x) {//递归输出路径
if (!x) return;
if (pre[x] != x) put(pre[x]);
vis[x] = 1;
printf("%d ", x);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++ i) {
int u, v;
scanf("%d", &u);
scanf("%d", &v);
addEdge(u, v + n, 1);
addEdge(v + n, u, 0);
}
for (int i = 1; i <= n; ++ i) {
addEdge(s, i, 1); addEdge(i, s, 0);
addEdge(i + n, t, 1); addEdge(t, i + n, 0);
}
for (int i = 1; i <= n; ++ i)
pre[i] = succ[i] = i;
int maxflow = 0, flow;
while (bfs())
while (flow = dinic(s, 0x3f3f3f3f))
maxflow += flow;
int ans = n - maxflow;
for (int i = n; i >= 1; -- i) {
if (succ[i] == i and !vis[i]) {//输出路径
put(i);
puts("");
}
}
printf("%d
", ans);
}
试题库问题
对于每一个题型 (i) ，都可以选择一个题目 (j) ，那么就从 (i) 到 (j) 连一条边
那么就是二分图多重匹配
可以拆点匈牙利做, 但效率低下
考虑网络流，
对于一个左部节点 (L) 它要匹配 (x) 个右部节点，就从源点连一条容量为 (x) 的边。
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 50000, oo = 0x3f3f3f3f;
int tot = 1, k, n, s, t;
int ver[N], edge[N], nxt[N], head[N];
vector<int> succ[N];
void add(int u, int v, int w) {
ver[++tot] = v;
edge[tot] = w;
nxt[tot] = head[u];
head[u] = tot;
ver[++tot] = u;
edge[tot] = 0;
nxt[tot] = head[v];
head[v] = tot;
}
int d[N];
bool bfs() {
queue<int> q;
memset(d, 0, sizeof d);
d[s] = 1; q.push(s);
while (q.size()) {
int u = q.front(), y; q.pop();
for (int i = head[u]; i; i = nxt[i]) {
if (edge[i] and !d[y = ver[i]]) {
d[y] = d[u] + 1;
if (y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow;
for (int i = head[u]; i and rest; i = nxt[i]) {
int v = ver[i];
if (edge[i] and d[v] == d[u] + 1) {
k = dinic(v, min(edge[i], rest));
if (!k) d[v] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
int m = 0;
scanf("%d%d", &k, &n);
s = 0, t = 5000;
for (int i = 1; i <= k; ++ i) {
int x; scanf("%d", &x); m += x;
add(s, i, x);
}
for (int i = 1; i <= n; ++ i) {
int num; scanf("%d", &num);
for (int j = 1; j <= num; ++ j) {
int x; scanf("%d", &x);
add(x, i + k, 1);
}
add(i + k, t, 1);
}
int flow, maxflow = 0;
while (bfs())
while (flow = dinic(s, +oo))
maxflow += flow;
if (m != maxflow)
{cout << "No Solution!" << endl; return 0;}
for (int i = 1; i <= k; ++ i) {
printf("%d: ", i);
for (int j = head[i]; j; j = nxt[j]) {
if (!edge[j] and ver[j] != s and ver[j] != t)//根据残量网络输出。
printf("%d ", ver[j] - k);
}
puts("");
}
}
最长不下降子序列问题
第一问直接做 (LIS)
第二问建模：若 (f[i]) 能转移到 (f[j]) , 才向 (i) 到 (j) 连边.
第三问直接在残量网络上将 (s) 到 (1) 与 (n) 到 (t) 扩容(要讨论)，继续找增广路。
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 50000, oo = 0x7f7f7f7f;
int n, s, t;
int tot = 1, edge[N], ver[N], nxt[N], d[N], f[N], head[N];
int a[N];
void add(int u, int v, int w) {
ver[++tot] = v;
edge[tot] = w;
nxt[tot] = head[u];
head[u] = tot;
ver[++tot] = u;
edge[tot] = 0;
nxt[tot] = head[v];
head[v] = tot;
}
int bfs() {
memset(d, 0, sizeof d);
queue<int> q;
q.push(s); d[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = nxt[i]) {
if (edge[i] and !d[ver[i]]) {
d[ver[i]] = d[u] + 1;
if (ver[i] == t) return 1;
q.push(ver[i]);
}
}
}
return 0;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow, v;
for (int i = head[u]; i and rest; i = nxt[i]) {
if (edge[i] and d[v = ver[i]] == d[u] + 1) {
k = dinic(v, min(edge[i], rest));
if (!k) d[v] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
scanf("%d", a + i);
for (int i = 1; i <= n; ++ i) {
f[i] = 1;
for (int j = 1; j < i; ++ j)
if (a[i] >= a[j])
f[i] = max(f[j] + 1, f[i]);
}
int ans = 0;
for (int i = 1; i <= n; ++ i)
ans = max(ans, f[i]);
cout << ans << endl;
int maxflow = 0, flow;
for (int i = 1; i <= n; ++ i)
for (int j = i + 1; j <= n; ++ j)
if (a[i] <= a[j] and f[j] == f[i] + 1)
add(i, j, 1);
s = 0, t = 1000;
for (int i = 1; i <= n; ++ i) {
if (f[i] == 1)
add(s, i, 1);
if (f[i] == ans) //想一想这里为什么不是"else if(f[i]==ans)"
add(i, t, 1); //调了我好久
}
while (bfs())
while (flow = dinic(s, +oo))
maxflow += flow;
cout << maxflow << endl;
add(s, 1, +oo);
if (f[n] == ans)//注意，只有满足f[n]==ans的才能连一条+oo的边到t
add(n, t, +oo);
while (bfs())
while (flow = dinic(s, +oo)) //新加边后残量网络上跑的最大流
maxflow += flow; //加上第二问的答案就是第三问答案
cout << maxflow << endl;
}
方格取数问题
二分图带权最大独立集
(Ans = sum - maxflow)
先对每个格子黑白相间地染色，分成左部节点与右部节点。
对于每个左部节点和右部节点都有一个权值，要求选出的点权值最大且没有连边
建边方法：
(1. s xRightarrow{val[L]} L)
(2. L xRightarrow{inf} R)
(3. R xRightarrow{val[R]}t)
跑出来的最大流就是答案。
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 50000, oo = 0x3f3f3f3f;
int n, m, s, t;
int tot = 1, edge[N], ver[N], nxt[N], head[N];
int val[200][200], id[200][200];
void add(int u, int v, int w) {
ver[++tot] = v;
edge[tot] = w;
nxt[tot] = head[u];
head[u] = tot;
ver[++tot] = u;
edge[tot] = 0;
nxt[tot] = head[v];
head[v] = tot;
}
const int tx[] = {1,0,-1,0};
const int ty[] = {0,1,0,-1};
void ADD(int x, int y) {
for (int i = 0; i < 4; ++ i) {
int nx = x + tx[i], ny = y + ty[i];
if (nx > 0 and nx <= n and ny > 0 and ny <= m)
add(id[x][y], id[nx][ny], +oo);
}
}
int d[N];
int bfs() {
memset(d, 0, sizeof d);
queue<int> q; q.push(s);
d[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = nxt[i]) {
if (edge[i] and !d[ver[i]]) {
d[ver[i]] = d[u] + 1;
if (ver[i] == t) return 1;
q.push(ver[i]);
}
}
}
return 0;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow;
for (int i = head[u]; i and rest; i = nxt[i]) {
if (edge[i] and d[ver[i]] == d[u] + 1) {
k = dinic(ver[i], min(edge[i], rest));
if (!k) d[ver[i]] = 0;
rest -= k;
edge[i] -= k;
edge[i ^ 1] += k;
}
}
return flow - rest;
}
int main() {
int cnt = 0, sum = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) {
int x; scanf("%d", &x);
sum += x;
id[i][j] = ++cnt;
val[i][j] = x;
}
s = 0, t = cnt + 11;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
if (i + j & 1) {
ADD(i,j);
add(s, id[i][j], val[i][j]);
} else
add(id[i][j], t, val[i][j]);
}
}
int maxflow = 0, flow;
while (bfs())
while (flow = dinic(s, +oo))
maxflow += flow;
printf("%d
", sum - maxflow);
return 0;
}
晨跑
由于每个点（除了1，n）只能经过一次，所以考虑拆点，然后连一条容量为1的边，跑最小费用最大流。
一个点只可以选一次，可以尝试拆点，连容量为1的边。
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 500000, oo = 0x3f3f3f3f;
int tot = 1, n, m, s, t, mincost;
int head[N], nxt[N], ver[N], edge[N], cost[N], d[5000];
bool vis[5000];
void add(int u, int v, int w, int c) {
ver[++tot] = v;
edge[tot] = w;
cost[tot] = c;
nxt[tot] = head[u];
head[u] = tot;
}
bool spfa() {
memset(d, 0x3f, sizeof d);
memset(vis, 0, sizeof vis);
queue<int> q; q.push(s);
vis[s] = 1; d[s] = 0;
while (q.size()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = nxt[i]) {
if (edge[i] and d[ver[i]] > d[u] + cost[i]) {
d[ver[i]] = d[u] + cost[i];
if (!vis[ver[i]])
q.push(ver[i]), vis[ver[i]] = 1;
}
}
}
return d[t] != d[0];
}
int dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow;
vis[u] = 1;
for (int i = head[u]; i and rest; i = nxt[i]) {
if ((!vis[ver[i]] or ver[i] == t) and edge[i] and d[ver[i]] == d[u] + cost[i]) {
k = dinic(ver[i], min(edge[i], rest));
if (!k) d[ver[i]] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
mincost += cost[i] * k;
}
}
return flow - rest;
}
int main() {
scanf("%d%d", &n, &m);
s = 1; t = n + n;
add(1, n + 1, +oo, 0), add(n + 1, 1, 0, 0);
add(n, n + n, +oo, 0), add(n + n, n, 0, 0);
for (int i = 2; i < n; ++ i)
add(i, i + n, 1, 0), add(i + n, i, 0, 0);
for (int i = 1; i <= m; ++ i) {
int x, y, z; scanf("%d%d%d", &x, &y, &z);
add(x + n, y, 1, z); add(y, x + n, 0, -z);
}
int maxflow = 0;
while (spfa()) {
vis[t] = 1;
while (vis[t]) {
memset(vis, 0, sizeof vis);
maxflow += dinic(s, +oo);
}
}
cout << maxflow << " " << mincost << endl;
}
[SCOI2007]修车
对于一个修车工先后修 (1) ～ (n) 的车，对答案的贡献就是：
(W_n × 1 + W_{n-1} × 2 + dots + W_1 × n)
所以我们考虑将每个工人拆成 (n) 个阶段的点，然后建二分图
对于每台车（左部节点）
它可以被这些工人中任意一位，任意一时刻被修理
则从这台车 (x) 连向右边的工人 (i) 的第 (j) 个阶段
对答案的贡献就是 (W(i,x) * j)
跑最小费用最大流即可
在直接建图不好算答案的时候不妨算贡献。
对于一个点有不同阶段，拆点的思想一定要有。
#include<bits/stdc++.h>
#define id(i,j) (i-1) * n + j
#pragma GCC optimize(2)
using namespace std;
const int N = 400000, oo = 0x3f3f3f3f;
int tot = 1, n, m, s, t;
int ver[N], nxt[N], edge[N], cost[N], head[N];
int d[N], vis[N], mincost, maxflow;
void add(int u, int v, int w, int c) {
ver[++tot] = v;
edge[tot] = w;
cost[tot] = c;
nxt[tot] = head[u];
head[u] = tot;
ver[++tot] = u;
edge[tot] = 0;
cost[tot] = -c;
nxt[tot] = head[v];
head[v] = tot;
}
int spfa() {
queue<int> q;
memset(vis, 0, sizeof vis);
memset(d, 0x3f, sizeof d);
d[s] = 0; vis[s] = 1; q.push(s);
while (q.size()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (edge[i] and d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return d[t] != d[N - 3];
}
int dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow;
vis[u] = 1;
for (int i = head[u]; i and rest; i = nxt[i]) {
int v = ver[i];
if ((!vis[v] or v == t) and edge[i] and d[v] == d[u] + cost[i]) {
k = dinic(v, min(edge[i], rest));
if (!k) d[v] = 0;
rest -= k;
edge[i] -= k;
edge[i ^ 1] += k;
mincost += k * cost[i];
}
}
return flow - rest;
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) {
int x; scanf("%d", &x);
for (int k = 1; k <= n; ++ k) {
add(i, n + id(j, k) , 1, x * k);
}
}
s = 0; t = n * m + n + 1;
for (int i = 1; i <= n; ++ i)
add(s, i, 1, 0);
for (int i = 1; i <= m; ++ i)
for (int j = 1; j <= n; ++ j)
add(n + id(i,j), t, 1, 0);
while (spfa()) {
vis[t] = 1;
while (vis[t]) {
memset(vis, 0, sizeof vis);
maxflow += dinic(s, +oo);
}
}
printf("%.2lf
", 1.0 * mincost / n);
}
[NOI2012]美食节
[SCOI2007]修车 的加强版
考虑到 (spfa) 是基于边数的，且每次做一次spfa最多只能找到一条增广路
所以想到优化边数
对于一个厨师第 (i) 阶段做第 (j) 道菜， 对于同一 (j) 发现费用是随 (i) 单增的，
所以包含这个厨师做 (j) 这个菜的增广路找到的顺序一定是 ((i,j)) , ((i+1, j)) , ((i+2, j)dots)
所以我们每跑完一次 (spfa) 再加 (i+1) 的那条边，优化了边数，就可以 (AC) 了。
网络流如果复杂度过不去，要考虑适时加边，优化边数。
详见代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 120000
#define inf 0x3f3f3f3f
int tot = 1, n, m, s, t, sum, ans;
int ver[N], edge[N], cost[N], nxt[N], incf[N], d[N], vis[N], pre[N], head[N];
void add(int u, int v, int w, int c) {
ver[++tot] = v; edge[tot] = w; cost[tot] = c; nxt[tot] = head[u]; head[u] = tot;
ver[++tot] = u; edge[tot] = 0; cost[tot] = -c;nxt[tot] = head[v]; head[v] = tot;
}
int p[N], c[3000][3000];
int Ek() {
memset(d, 0x3f, sizeof d); memset(vis, 0, sizeof d); pre[t] = 0;
d[s] = 0; vis[s] = 1; queue<int> q; q.push(s);
incf[s] = inf;
while (q.size()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (edge[i] and d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i]; pre[v] = i;
incf[v] = min(incf[u], edge[i]);
if (!vis[v])
vis[v] = 1, q.push(v);
}
}
}
if (!pre[t]) return 0;
for (int u = t; u != s; u = ver[pre[u] ^ 1]) {
int e = pre[u];
edge[e] -= incf[t];
edge[e ^ 1]+= incf[t];
ans += incf[t] * cost[e];
}
return 1;
}
int dish[N], cook[N];
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;//n种菜，m个厨师
for (int i = 1; i <= n; ++ i) cin >> p[i], sum += p[i];//sum个阶段
s = 0, t = N - 2;
for (int i = 1; i <= n; ++ i)
add(s, i + sum * m, p[i], 0);//对于每种菜，从源点连一条容量为该种菜数量的边
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) {
cin >> c[i][j];
add(i + sum * m, (j - 1) * sum + 1, 1, c[i][j]);
//第一阶段连边
}
for (int i = 1; i <= m; ++ i)
add((i - 1) * sum + 1, t, 1, 0);//向汇点连边
for (int i = 1; i <= m; ++ i)
for (int j = 1; j <= sum; ++ j) {
int tmp = (i - 1) * sum + j;
dish[tmp] = j; cook[tmp] = i;//一个映射: tmp这个点是第j个菜(阶段), 由i这个厨师来做
}
while (Ek()) {
int tmp = ver[pre[t] ^ 1];
add(tmp + 1, t, 1, 0);//下个阶段连边
for (int i = 1; i <= n; ++ i)
add(i + m * sum, tmp + 1, 1, c[i][cook[tmp]] * (dish[tmp] + 1));
}
cout << ans << endl;
}
[ZJOI2010]网络扩容
第一问裸的最大流，
第二问考虑将每条路都扩容，
就在原图的基础上每个点再加一条容量为 (inf)，有费用的边；
表示可以无线扩容，每扩容一点流量，就花费一点价值；
为了限制扩容的流量为 (k)，从 (n xRightarrow{(k,0)} n+1, t leftarrow n+1);
从 (s) 到 (t) 跑最小费用最大流即可
网络流重边：一条边没有费用，一条边有费用，可以表示当一个东西超出某一限制后才会产生费用。
#include<bits/stdc++.h>
using namespace std;
const int N = 60000, inf = 0x3f3f3f3f;
int n, m, incf[N], s, t, a[N], b[N], c[N];
int tot = 1, head[N];
int ver[N], edge[N], cost[N], nxt[N];
bool vis[N];
int pre[N];
void add(int u, int v, int w, int c) {
ver[++tot] = v;
edge[tot] = w;
cost[tot] = c;
nxt[tot] = head[u];
head[u] = tot;
ver[++tot] = u;
edge[tot] = 0;
cost[tot] = -c;
nxt[tot] = head[v];
head[v] = tot;
}
int d[N];
int bfs() {
memset(d, 0, sizeof d);
queue<int> q; q.push(s);
d[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (edge[i] and !d[v]) {
d[v] = d[u] + 1;
if (v == t) return 1;
q.push(v);
}
}
}
return 0;
}
int mincost = 0;
int dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow;
for (int i = head[u]; i and rest; i = nxt[i]) {
int v = ver[i];
if (edge[i] and d[v] == d[u] + 1) {
k = dinic(v, min(edge[i], rest));
if (!k) d[v] = 0;
rest -= k;
edge[i] -= k;
edge[i ^ 1] += k;
}
}
return flow - rest;
}
int Dinic(int u, int flow) {
if (u == t) return flow;
int k, rest = flow;
vis[u] = 1;
for (int i = head[u]; i and rest; i = nxt[i]) {
int v = ver[i];
if ((!vis[v] or v == t) and edge[i] and d[v] == d[u] + cost[i]) {
k = Dinic(v, min(edge[i], rest));
if (!k) d[v] = 0;
rest -= k;
edge[i] -= k;
edge[i ^ 1] += k;
mincost += k * cost[i];
}
}
return flow - rest;
}
int spfa() {
memset(d, 0x3f, sizeof d);
memset(vis, 0, sizeof vis);
queue<int> q; q.push(s);
int M = d[0];
d[s] = 0; vis[s] = 1;
while (q.size()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (edge[i] and d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
if (!vis[v])
q.push(v), vis[v] = 1;
}
}
}
return d[t] < M;
}
int zkw() {
while (spfa()) {
vis[t] = 1;
while (vis[t]) {
memset(vis, 0, sizeof vis);
Dinic(s, inf);
}
}
return mincost;
}
int z[N];
int main() {
ios::sync_with_stdio(0);
int k;
cin >> n >> m >> k;
for (int i = 1; i <= m; ++ i) {
cin >> a[i] >> b[i] >> c[i] >> z[i];
add(a[i], b[i], c[i], 0);
}
s = 1, t = n;
int ans1 = 0, flow;
while (bfs())
while (flow = dinic(s, inf))
ans1 += flow;
cout << ans1 << " ";
t ++; tot = 1;
memset(head, 0, sizeof head);
for (int i = 1; i <= m; ++ i) {
add(a[i], b[i], c[i], 0);
add(a[i], b[i], inf, z[i]);
}
add(t - 1, t, k + ans1, 0);
cout << zkw() << endl;
}