2236. 伊基的故事 I - 道路重建
2026-07-24
题解
由于原图就已经是一个流网络了,我们不妨来看看改变一条就能增加流量的边的条件:
- 由于它能在容量扩大后增大原网络的最大流,则在原图中,它的流量一定等于容量,即 f(u,v)=c(u,v)。
- 与上面相似,我们需要让 S,T 在残留网络上能到达这个边的两个端点。
综上,我们可以先跑出最大流,然后在残留网络上从 S 和 T 跑 DFS,标记出所有能到达的点,然后枚举每条流量等于容量的边,看它两端是否可达即可。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 510 , M = (5000+N)*2+10;
const int INF = 0x3f3f3f3f;
int n , m , S , T;
int h[N] , e[M] , ne[M] , w[M] , idx;
int q[N] , d[N] , cur[N];
bool stS[N] , stT[N];
void add(int a , int b , int c) {
w[idx] = c , e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
w[idx] = 0 , e[idx] = a , ne[idx] = h[b] , h[b] = idx ++;
}
int find(int u , int limit) {
if(u == T) return limit;
int flow = 0;
for(int i = cur[u] ; ~i && flow < limit ; i = ne[i]) {
cur[u] = i;
int v = e[i];
if(d[v] == d[u]+1 && w[i]) {
int t = find(v , min(w[i] , limit-flow));
if(!t) d[v] = -1;
flow += t; w[i] -= t; w[i^1] += t;
}
}
return flow;
}
bool bfs() {
memset(d , -1 , sizeof d);
int hh = 0 , tt = -1;
q[++ tt] = S; d[S] = 0; cur[S] = h[S];
while(hh <= tt) {
int t = q[hh ++];
for(int i = h[t] ; ~i ; i = ne[i]) {
int v = e[i];
if(d[v] == -1 && w[i]) {
d[v] = d[t] + 1;
cur[v] = h[v];
if(v == T) return true;
q[++ tt] = v;
}
}
}
return false;
}
int dinic() {
int r = 0 , flow;
while(bfs()) while((flow = find(S , INF))) r += flow;
return r;
}
void dfs(int u , bool st[] , int t) {
st[u] = true;
for(int i = h[u] ; ~i ; i = ne[i]) {
int j = i^t , v = e[i];
if(w[j] && !st[v]) dfs(v , st , t);
}
}
int main() {
scanf("%d%d" , &n , &m);
S = 0; T = n-1;
memset(h , -1 , sizeof h);
for(int i = 1 ; i <= m ; i ++) {
int a , b , c; scanf("%d%d%d" , &a , &b , &c);
add(a , b , c);
}
dinic();
dfs(S , stS , 0);
dfs(T , stT , 1);
int res = 0;
for(int i = 0 ; i < idx ; i += 2) {
if(!w[i] && stS[e[i^1]] && stT[e[i]]) res ++;
}
printf("%d\n" , res);
return 0;
}