必要的注释已经加上了
/*
* 这题说的是有一个最大流问题,要求你找出来关键边。
* 关键边的定义就是我把这条边的容量扩大的话,整个网络的最大流也会得到提升
* 这个要你自己想的话太难的,直接告诉你做法吧,然后来证明正确性。
* 很明显如果某条边是不满的话你增加了是没用的,瓶颈肯定不会在这些不满的边上。
* 我们先任意求一个最大流,找满流的边,那什么时候这条边扩容的话就可以使得流量增加呢?
* 假设这条边是(u, v)的话,应该要求在residual network里面s可以走到u并且v可以走到t吧
* 那反过来呢,这个时候u一定可以走到s吗?不一定。
* 因为在残留网络里面w(u, v) = c(u, v) - f(u, v), w(v, u) = f(u, v)
* 所以s能走过来不代表u能走回去。那这个时候应该深搜吧。
* 反过来也是正确的,如果一条边(u, v)的容量增加可以使得网络流的流量增加,
* 那么应该在Gf里面s可以走到u并且v可以走到t吧。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 550, M = 5050 << 1;
int n, m, S, T;
int fi[N], ne[M], en[M], w[M], idx = 0;
int cap[M];
void add(int a, int b, int c) {
idx++;
ne[idx] = fi[a];
fi[a] = idx;
en[idx] = b;
w[idx] = c;
}
int q[N], head, tail, d[N], cur[N];
bool bfs() {
for (int i = 1; i <= n; i++) d[i] = -1;
head = 1, tail = 0;
d[S] = 0, cur[S] = fi[S], q[++tail] = S;
while (tail - head + 1 > 0) {
int u = q[head++];
for (int p = fi[u]; p > 0; p = ne[p]) {
int v = en[p];
if (d[v] != -1 || !w[p]) continue;
d[v] = d[u] + 1, cur[v] = fi[v], q[++tail] = v;
if (v == T) return true;
}
}
return false;
}
int find(int u, int minw) {
if (u == T) return minw;
for (int p = cur[u]; p > 0; p = ne[p]) {
int v = en[p];
if (d[v] != d[u] + 1 || !w[p]) continue;
int res = find(v, min(minw, w[p]));
if (!res) { cur[u] = ne[p]; continue; }
w[p] -= res;
if (p % 2 == 0) w[p - 1] += res;
else w[p + 1] += res;
return res;
}
return 0;
}
int dinic() {
int r = 0;
while (bfs()) {
while (true) {
int flow = find(S, 1e8);
if (flow == 0) break;
r += flow;
}
}
return r;
}
int gofromandto[N];
int fireverse[N], enreverse[M], nereverse[M], wreverse[M], idxreverse = 0;
void addreverse(int a, int b, int c) {
idxreverse++;
nereverse[idxreverse] = fireverse[a];
fireverse[a] = idxreverse;
enreverse[idxreverse] = b;
wreverse[idxreverse] = c;
}
void buildreverse() {
for (int i = 1; i <= n; i++) {
for (int p = fi[i]; p > 0; p = ne[p]) {
int v = en[p];
addreverse(v, i, w[p]);
}
}
}
// 建一个反图,其实不建也可以啦,但是建出来之后可以直接写深搜就比较方便
// 不建的话你要判断在最后的残留网络里面哪些点可以走到t是比较麻烦的
void dfs1(int u, int dad) {
for (int p = fi[u]; p > 0; p = ne[p]) {
int v = en[p];
if (gofromandto[v] != 0 || v == dad || w[p] == 0) continue;
gofromandto[v] = 1;
dfs1(v, u);
}
}
void dfs2(int u, int dad) {
for (int p = fireverse[u]; p > 0; p = nereverse[p]) {
int v = enreverse[p];
if (gofromandto[v] != 0 || v == dad || wreverse[p] == 0) continue;
gofromandto[v] = 2;
dfs2(v, u);
}
}
struct edge {
int a, b;
}e[M];
int main() {
scanf_s("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf_s("%d%d%d", &a, &b, &c);
add(a + 1, b + 1, c); add(b + 1, a + 1, 0);
cap[idx - 1] = c;
e[i].a = a + 1, e[i].b = b + 1;
}
S = 1, T = n;
dinic();
gofromandto[S] = 1;
gofromandto[T] = 2;
buildreverse();
dfs1(S, 0);
dfs2(T, 0);
int res = 0;
// 应该是一条边一条边地看过来吧
for (int i = 1; i <= m; i ++ ) {
int a = e[i].a, b = e[i].b;
if (gofromandto[a] != 1 || gofromandto[b] != 2) continue;
if (cap[2 * i - 1] == w[2 * i] && w[2 * i - 1] == 0) res++;
}
printf_s("%d\n", res);
}
// 好的上面的代码已经AC了,2021年8月20日14:32:02
上面要注意的点就是if (cap[2 * i - 1] == w[2 * i] && w[2 * i - 1] == 0) res++;这个判断,要搞清楚编号是奇数的边跟编号是偶数的边在残留网络里面分别代表什么。