第一问是直接建图跑最大流
第二问需要在跑完第一问的残量网络上建图，对于正向边建容量是inf,费用是扩容费用的边，反向边建容量为0，费用是负的扩容费用的边，最后加一条边限流
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define pb push_back
#define read2(a, b) (read(a), read(b))
#define read3(a, b, c) (read(a), read(b), read(c))
#define lop(i,a,b) for(register int i = (a); i <= (b); ++i)
#define dlop(i,a,b) for(register int i = (a); i >= (b); --i)
#define eps (1e-7)
#define fir first
#define sec second
const int inf = 0x3f3f3f3f-1;
const int MAXN = 1e3+7;
const int MAXM = 5e3+7;
typedef long long LL;
typedef long double LF;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef unsigned int uint;
template<class T> void read(T & x) {
register int c = getchar(), f = 1;x = 0;
while(!isdigit(c)) {if (c == '-') f = -f;c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
int n, m, k, maxflow, dep[MAXN], s, t, cur[MAXN], head[MAXN], ans;
struct Edge {
int u, v, w, c, next, t;
} G[MAXM<<2];
int tot = 1, dis[MAXN];
bool inq[MAXN];
inline void add1(int u, int v, int w, int c) {
G[++tot] = (Edge) {u, v, w, 0, head[u], c}; head[u] = tot;
}
inline void add2(int u, int v, int w, int c) {
G[++tot] = (Edge) {u, v, w, c, head[u], 0}; head[u] = tot;
}
bool bfs(int s, int t) {
memset(dep, 0x7f, sizeof dep);
memcpy(cur+1, head+1, n*4+4);
queue<int>q;
while(!q.empty()) q.pop();
dep[s] = 0;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i; i = G[i].next) {
int v = G[i].v, w = G[i].w;
if (dep[v] > inf && w) {
dep[v] = dep[u] + 1;
if (v == t) return 1;
q.push(v);
}
}
}
return dep[t] < inf;
}
int dfs(int u, int t, int limit) {
if (u == t || !limit) return limit;
int flow = 0, f;
for(int i = cur[u]; i; i = G[i].next) {
cur[u] = i;
int v = G[i].v, w = G[i].w;
if (dep[v] == dep[u] + 1 && (f = dfs(v, t, min(w, limit)))) {
flow += f;
limit -= f;
G[i].w -= f;
G[i^1].w += f;
if (!limit) break;
}
}
return flow;
}
void dinic(int s, int t) {
while(bfs(s, t)) maxflow += dfs(s, t, inf);
}
bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof dis);
memset(inq, 0, sizeof inq);
queue<int>q; q.push(s); dis[s] = 0, inq[s] = 1;
while(!q.empty()) {
int u = q.front();
inq[u] = 0;
q.pop();
for(int i = head[u]; i; i = G[i].next) {
int v = G[i].v, w = G[i].w, c = G[i].c;
if (dis[v] > dis[u] + c && w) {
dis[v] = dis[u] + c;
cur[v] = i;
if (!inq[v]) q.push(v), inq[v] = 1;
}
}
}
return dis[t] < inf;
}
void update(int s, int t) {
int i, x = inf;
for(i = cur[t]; i; x = min(x, G[i].w), i = cur[G[i].u]);
for(i = cur[t]; i; G[i].w -= x, G[i^1].w += x, ans += x * G[i].c, i = cur[G[i].u]);
}
void EK(int s, int t) {
while(spfa(s, t)) update(s, t);
}
int main(void) {
// freopen("1.in", "r", stdin);
read3(n, m, k);
for(int i = 1; i <= m; ++i) {
static int u, v, w, c;
read3(u, v, w); read(c);
add1(u, v, w, c), add1(v, u, 0, -c);
}
dinic(1, n);
printf("%d ", maxflow);
int ss = tot;
for(int i = 2; i <= ss; i += 2)
add2(G[i].u, G[i].v, inf, G[i].t),
add2(G[i].v, G[i].u, 0, -G[i].t);
add1(n, n+1, k, 0);
memset(cur, 0, sizeof cur);
EK(1, n+1);
printf("%d
", ans);
return 0;
}