【题目来源】
【题目描述】
伊基是一个小国 – 凤凰国的国王。凤凰国是如此之小，以至于只有一个城市负责日常商品的生产，并使用公路网将商品运送到首都。
伊基发现本国最大的问题在于运输速度太慢了。因为伊基以前是 ACM/ICPC 的参赛者，他意识到这其实是一个最大流问题。他编写了一个最大流程序，并计算出了当前运输网络的最大运输能力。
他对运输速度的现状十分不满，并希望能够提高国家的运输能力。
提高运输能力的方法很简单，伊基将在运输网络中重建一些道路，以使这些道路具有更高的运输能力。但是不幸的是，凤凰国的财力有限，道路建设经费只够重建一条道路。伊基想要知道共有多少条道路可以纳入重建道路候选名单。这些道路需要满足，将其重建后，国家的总运输能力能够增加。
【输入格式】
第一行包含 N 和 M，分别表示城市和道路的数量。
接下来 M 行，每行包含三个整数 a,b,c，表示存在一条道路从城市 a 通往城市 b，且运输能力为 c。所有道路都是有方向的。
城市编号从 0 到 N−1。生产日常商品的城市为 0 号城市，首都为 N−1 号城市。
【输出格式】
输出一个整数 K，表示存在 K 条道路，对其中每条道路进行重建都会增加运输网络的运输能力。
【输入样例】
2 1
0 1 1
【输出样例】
1
【数据范围】
1≤N≤500,
1≤M≤5000,
0≤a,b<N,
0≤c≤100
【算法分析】
Dinic算法：
【算法代码】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=5e2+5,M=2e4+5;
const int INF=0x3f3f3f3f;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]; //edgevoid 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 hh=0,tt=0;q[0]=S,d[S]=0;while(hh<=tt) {int u=q[hh++];for(int i=h[u]; ~i; i=ne[i]) {int v=e[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(u==T) return lim;int flow=0;for(int i=cur[u]; ~i && flow<lim; i=ne[i]) {cur[u]=i;int v=e[i];if(d[v]==d[u]+1 && f[i]) {int t=dfs(v,min(f[i],lim-flow));if(!t) d[v]=-1;f[i]-=t,f[i^1]+=t,flow+=t;}}return flow;
}LL dinic() {LL r=0,flow=0;while(bfs()) {for(int i=0; i<n; i++) cur[i]=h[i];while(flow=dfs(S,INF)) r+=flow;}return r;
}void dfs1(int u) { //points that can be reached from Svis_s[u]=1;for(int i=h[u]; ~i; i=ne[i]) {int v=e[i];if(!vis_s[v] && f[i]) dfs1(v);}
}void dfs2(int u) { //Be able to reach point Tvis_t[u]=1;for(int i=h[u]; ~i; i=ne[i]) {int v=e[i];if(!vis_t[v] && f[i^1]) dfs2(v);}
}int main() {memset(h,-1,sizeof h);cin>>n>>m;S=0, T=n-1;for(int i=0; i<m; i++) {int a,b,c;cin>>a>>b>>c;ea[i]=a,eb[i]=b,eid[i]=idx;add(a,b,c);}dinic();dfs1(S), dfs2(T);int ans=0;for(int i=0; i<m; i++) {int a=ea[i],b=eb[i],idx=eid[i];if(f[idx]==0 && vis_s[a] && vis_t[b]) ans++;}cout<<ans<<endl;return 0;
}/*
in:
2 1
0 1 1out:
1
*/
【参考文献】