AcWing 2236：伊基的故事 I - 道路重建 ← 最大流之关键边 + Dinic算法

【题目来源】https://www.acwing.com/problem/content/2238/【题目描述】伊基是一个小国 – 凤凰国的国王。凤凰国是如此之小以至于只有一个城市负责日常商品的生产并使用公路网将商品运送到首都。伊基发现本国最大的问题在于运输速度太慢了。因为伊基以前是 ACM/ICPC 的参赛者他意识到这其实是一个最大流问题。他编写了一个最大流程序并计算出了当前运输网络的最大运输能力。他对运输速度的现状十分不满并希望能够提高国家的运输能力。提高运输能力的方法很简单伊基将在运输网络中重建一些道路以使这些道路具有更高的运输能力。但是不幸的是凤凰国的财力有限道路建设经费只够重建一条道路。伊基想要知道共有多少条道路可以纳入重建道路候选名单。这些道路需要满足将其重建后国家的总运输能力能够增加。【输入格式】第一行包含 N 和 M分别表示城市和道路的数量。接下来 M 行每行包含三个整数 a,b,c表示存在一条道路从城市 a 通往城市 b且运输能力为 c。所有道路都是有方向的。城市编号从 0 到 N−1。生产日常商品的城市为 0 号城市首都为 N−1 号城市。【输出格式】输出一个整数 K表示存在 K 条道路对其中每条道路进行重建都会增加运输网络的运输能力。【输入样例】2 10 1 1【输出样例】1【数据范围】1≤N≤500,1≤M≤5000,0≤a,bN,0≤c≤100【算法分析】Dinic算法https://blog.csdn.net/hnjzsyjyj/article/details/161317988【算法代码】#include bits/stdc.h using namespace std; typedef long long LL; const int N5e25,M2e45; const int INF0x3f3f3f3f; int n,m,S,T; int h[N],e[M],ne[M],f[M],idx; int d[N],cur[N],q[N]; bool vis_s[N],vis_t[N]; int ea[M],eb[M],eid[M]; //edge void add(int a,int b,int c) { f[idx]c,e[idx]b,ne[idx]h[a],h[a]idx; f[idx]0,e[idx]a,ne[idx]h[b],h[b]idx; } bool bfs() { memset(d,-1,sizeof d); int hh0,tt0; q[0]S,d[S]0; while(hhtt) { int uq[hh]; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(d[v]-1 f[i]) { d[v]d[u]1; q[tt]v; } } } return d[T]!-1; } int dfs(int u,int lim) { if(uT) return lim; int flow0; for(int icur[u]; ~i flowlim; ine[i]) { cur[u]i; int ve[i]; if(d[v]d[u]1 f[i]) { int tdfs(v,min(f[i],lim-flow)); if(!t) d[v]-1; f[i]-t,f[i^1]t,flowt; } } return flow; } LL dinic() { LL r0,flow0; while(bfs()) { for(int i0; in; i) cur[i]h[i]; while(flowdfs(S,INF)) rflow; } return r; } void dfs1(int u) { //points that can be reached from S vis_s[u]1; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(!vis_s[v] f[i]) dfs1(v); } } void dfs2(int u) { //Be able to reach point T vis_t[u]1; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(!vis_t[v] f[i^1]) dfs2(v); } } int main() { memset(h,-1,sizeof h); cinnm; S0, Tn-1; for(int i0; im; i) { int a,b,c; cinabc; ea[i]a,eb[i]b,eid[i]idx; add(a,b,c); } dinic(); dfs1(S), dfs2(T); int ans0; for(int i0; im; i) { int aea[i],beb[i],idxeid[i]; if(f[idx]0 vis_s[a] vis_t[b]) ans; } coutansendl; return 0; } /* in: 2 1 0 1 1 out: 1 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161471616https://blog.csdn.net/hnjzsyjyj/article/details/161317988https://blog.csdn.net/hnjzsyjyj/article/details/161438841https://blog.csdn.net/hnjzsyjyj/article/details/161441409https://blog.csdn.net/hnjzsyjyj/article/details/161446211