题目链接：https://www.luogu.com.cn/problem/solution/P2604
这一眼就是网络流题目 第一问十分简单，直接最大流即可 那么怎么做第二问呢？
我们观察到，先算出了第一问的
m
a
x
f
l
o
w
maxflow
maxflow，然后第二问等价于在原图中（原图中每条边费用为0），每条边加上一条流量为
∞
\infty
∞，费用为原边的费用的图
然后根据最大流最小费用算法，我们可以知道其实是不用重新建整个图，只需要在当前残量网络中加上原图没有的边即可
这是因为最大流最小费用算法每次会找出费用最小的一条增广路，我们求最大流时每条增广路费用均为0，一定符合条件
C
o
d
e
Code
Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std
;
const int MAXN
= 1000, MAXM
= 1e4, inf
= 1 << 30;
struct w
{int to
, nx
, f
, c
;}head
[MAXM
+ MAXM
+ 10];
struct edge
{int x
, y
, f
, c
;}e
[MAXM
+ 10];
int a
[MAXN
+ 10], vis
[MAXN
+ 10], dis
[MAXN
+ 10], minf
[MAXN
+ 10], lx
[MAXN
+ 10], tot
= 1;
inline int read();
inline void add(int x
, int y
, int i
, int f
, int c
){head
[i
].to
= y
, head
[i
].nx
= a
[x
], head
[i
].f
= f
, head
[i
].c
= c
; a
[x
] = i
;}
inline void add_edge(int x
, int y
, int f
, int c
){
add(x
, y
, ++tot
, f
, c
);
add(y
, x
, ++tot
, 0, -c
);
}
bool spfa(int s
, int t
, int n
){
queue
<int> q
;
for (register int i
= 1; i
<= n
; ++i
) dis
[i
] = inf
, vis
[i
] = 0;
dis
[s
] = 0; minf
[s
] = inf
; q
.push(s
);
while (!q
.empty()){
int x
= q
.front(); q
.pop(); vis
[x
] = 0;
for (register int i
= a
[x
]; i
; i
= head
[i
].nx
){
int v
= head
[i
].to
;
if (head
[i
].f
&& dis
[v
] > dis
[x
] + head
[i
].c
){
dis
[v
] = dis
[x
] + head
[i
].c
;
minf
[v
] = min(minf
[x
], head
[i
].f
);
lx
[v
] = i
;
if (!vis
[v
]){
vis
[v
] = 1;
q
.push(v
);
}
}
}
}
return dis
[t
] < inf
;
}
int MCMF(int s
, int t
, int n
, int op
){
int maxflow
= 0, mincost
= 0;
while (spfa(s
, t
, n
)){
maxflow
+= minf
[t
];
mincost
+= dis
[t
] * minf
[t
];
int tmp
= t
;
while (tmp
!= s
){
head
[lx
[tmp
]].f
-= minf
[t
];
head
[lx
[tmp
] ^ 1].f
+= minf
[t
];
tmp
= head
[lx
[tmp
] ^ 1].to
;
}
}
if (op
) return maxflow
;
else return mincost
;
}
int main(){
int n
, m
, k
;
n
= read(), m
= read(), k
= read();
for (register int i
= 1; i
<= m
; ++i
){
e
[i
].x
= read(), e
[i
].y
=read(), e
[i
].f
= read(), e
[i
].c
= read();
add_edge(e
[i
].x
, e
[i
].y
, e
[i
].f
, 0);
}
int maxflow
= MCMF(1, n
, n
, 1);
printf("%d ", maxflow
);
add_edge(n
+ 1, 1, k
, 0);
for (register int i
= 1; i
<= m
; ++i
) add_edge(e
[i
].x
, e
[i
].y
, inf
, e
[i
].c
);
int mincost
= MCMF(n
+ 1, n
, n
+ 1, 0);
printf("%d\n", mincost
);
return 0;
}
inline int read(){
int x
= 0;
char c
= getchar();
while (!isdigit(c
))c
= getchar();
while (isdigit(c
))x
= (x
<< 1) + (x
<< 3) + (c
& 15), c
= getchar();
return x
;
}
