第一问跑最大流，第二问新建一条边连接0和1，流量为上第一问的答案+k,费用为0，接下来图中每条边拆成两条边，第一条容量为C费用为0，第二条容量无穷费用为W，再跑一遍费用流即可。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<set>
#include<queue>
#define mp make_pair
#define inf 0x37373737
#define N 30050
#define M 30050
using namespace std;
struct Dinic {
int s, t, n, pre[N], cur[N], h[N], level[N], sign, q[N];
int cap[M], to[M], ne[M], flow, e;
void liu(int u, int v, int w) {
to[e] = v, ne[e] = h[u], cap[e] = w;
h[u] = e++;
}
void link(int u, int v, int w) {
liu(u, v, w);
liu(v, u, );
}
void init(int n) {
for (int i = ; i <= n; ++i)
h[i] = -;
e = ;
}
bool bfs() {
int L = , R = ;
fill(level, level + n, -);
sign = q[R++] = t;
level[t] = ;
while (L < R && level[s] == -) {
int c = q[L++];
for (int k = h[c]; ~k; k = ne[k]) {
if (cap[k ^ ] > && level[to[k]] == -)
level[to[k]] = level[c] + , q[R++] = to[k];
}
}
return ~level[s];
}
void push() {
int pl = inf, p, k;
for (p = t; p != s; p = to[k ^ ]) {
k = pre[p];
pl = min(pl, cap[k]);
}
for (p = t; p != s; p = to[k ^ ]) {
k = pre[p];
cap[k] -= pl;
cap[k ^ ] += pl;
if (cap[k] == )
sign = to[k ^ ];
}
flow += pl;
}
void dfs(int c) {
if (c == t)
push();
else {
for (int &k = cur[c]; ~k; k = ne[k])
if (cap[k] > && level[to[k]] + == level[c]) {
pre[to[k]] = k;
dfs(to[k]);
if (level[sign] > level[c])
return;
sign = t;
}
level[c] = -;
}
}
int run(int _s, int _t, int _n) {
s = _s, t = _t, n = _n;
flow = ;
while (bfs()) {
for (int i = ; i < n; ++i)
cur[i] = h[i];
dfs(s);
}
return flow;
}
} mf; struct MCMF{
int h[N] , dis[N] , ing[N] , pre[N] , s , t , n;
int to[M] , ne[M] , cap[M] , cost[M] , e;
void ini(){
fill(h,h+N,-);
e = ;
}
void liu(int u,int v,int c,int w){
to[e] = v , ne[e] = h[u] , cap[e] = c , cost[e] = w;
h[u] = e++;
}
void link(int u,int v,int c,int w){
liu(u,v,c,w);
liu(v,u,,-w);
}
bool spfa(){
queue<int> Q;
fill(ing,ing+n,);
fill(pre,pre+n,-);
fill(dis,dis+n,inf);
ing[s] = true , dis[s] = ;
Q.push(s);
while(!Q.empty()){
int c = Q.front();Q.pop();ing[c] = false;
for(int k=h[c];~k;k=ne[k]){
int v = to[k];
if(cap[k] <= ) continue;
if(dis[c] + cost[k] < dis[v]){
dis[v] = dis[c] + cost[k];
pre[v] = k;
if(!ing[v]) Q.push(v) , ing[v] = true;
}
}
}
return dis[t] != inf;
}
int flow , mincost;
pair<int,int> run(int _s,int _t,int _n){
s = _s , t = _t , n = _n;
flow = mincost = ;
while(spfa()){
int pl = inf , p , k;
for(p=t;p!=s;p=to[k^]){
k = pre[p];
pl = min(pl,cap[k]);
}
for(p=t;p!=s;p=to[k^]){
k = pre[p];
cap[k] -= pl;
cap[k^] += pl;
}
mincost += pl * dis[t];
flow += pl;
}
return mp(flow,mincost);
}
};
MCMF mcmf; int n,m,k,i,a,b,c,d,flow,cost;
int main()
{
scanf("%d%d%d",&n,&m,&k);
mf.init(n+);
mcmf.ini();
for (i=;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
mf.link(a,b,c);
mcmf.link(a,b,c,);
mcmf.link(a,b,,d);
}
flow=mf.run(,n,n+);
mcmf.link(,,flow+k,);
printf("%d %d",flow,mcmf.run(,n,n+).second);
}