题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4240
题意：求最大流/一条流量最大的路的流量
分析：
每次增广的时候更新流量，保存最大的那条，这种做法显然是错误的，因为无论是dinic
还是isap，在取得增光路时都与存边的前后顺序或者增广的先后顺序有关。
就比如
1 1 4 4 1 3 1 2 5 2 3 5 2 3 2 2 3 3
如果用前向星存的图，那么从2这个顶点肯定先去增广容量为3的边，然后增广容量为2的
边，容量为5的边是无法得到增广的，所以答案就错误了。
这是因为一条路的最大流可能会被岔开。
那么求一条流量最大的路，怎么求才是正确的呢？
方法一：
对于这个题，可以用深搜，搜出流量最大的路，然后跑一下最大流，就可以得出答案了。
AC代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int maxn = 1002, maxe = 500005; const int INF = 0x3f3f3f3f; int eid, sflow, s, t, n, m; int head[maxn], lev[maxn], cur[maxn]; bool vis[maxn]; struct Edge { int to, cap, nxt; Edge(){} Edge(int t, int c, int nx):to(t), cap(c), nxt(nx){} }edge[maxe]; void inline AddEdge(int u, int v, int cap) { edge[eid] = Edge(v, cap, head[u]); head[u] = eid++; edge[eid] = Edge(u, 0, head[v]); head[v] = eid++; } void inline init() { sflow = eid = 0; memset(head, -1, sizeof(head)); memset(vis, false, sizeof(vis)); } void dfsget(int u, int mins)//预处理出最大的一条流量 { if(mins < sflow) return ; if(u == t) { if(mins > sflow) sflow = mins; return; } for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to; if(vis[v] == false) { vis[v] = true; dfsget(v, min(mins, edge[i].cap)); vis[v] = false; } } } bool BFS() { queue<int> q; memset(vis, false, sizeof(vis)); vis[s] = true; lev[s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to, c = edge[i].cap; if(!vis[v] && c > 0) { vis[v] = true; lev[v] = lev[u] + 1; q.push(v); } } } return vis[t]; } int dfs(int u, int a) { if(u == t || a == 0) return a; int flow = 0, f; for(int &i = cur[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to, c = edge[i].cap, r = i^1; if(lev[v] == lev[u] + 1 && c > 0 && (f = dfs(v, min(c, a))) > 0) { edge[i].cap -= f; edge[r].cap += f; flow += f; a -= f; if(a == 0) break; } } if(flow == 0) lev[u] = -1; return flow; } int dinic() { int ret = 0; while(BFS()) { for(int i = 0; i <= n; i++) cur[i] = head[i]; int f = INF; f = dfs(s, f); ret += f; } return ret; } int main() { int T, kase, u, v, w; scanf("%d", &T); while(T--) { scanf("%d%d%d%d%d", &kase, &n, &m, &s, &t); init(); for(int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); AddEdge(u, v, w); } vis[s] = true; dfsget(s, INF); int maxflow = dinic(); printf("%d %.3lf\n", kase, maxflow*1.0/sflow); } return 0; }方法二：
用广搜每次增广出由一条路构成的最大流量，注意是一条路，意味着只有一条流汇入汇点，而且这条流
是当前最大的。那么第一次增广得到的就是一条路能够取得到的最大流。这种做法在实现上有一定的技
巧性。具体做法是，从源点开始bfs，用优先队列使得能够获得流量大点处于队首，那么每次都是从流量
最大点出去bfs的，即使它后面连接的路流量小了，也会被流量更大的路取代，进而处于队首。当一个点
bfs到汇点时，如果优先队列中有流量更大的边，那么这条边所连接的点是处于队首的，所以会接着增广。
注意，这种做法中，每一条边的容量限定次数可以被放大。
还有，对于网上的
1
1 7 8 1 5 1 2 5 2 3 2 3 5 2 2 4 3 4 5 3 2 6 5 6 7 5 7 5 5
这组数据，我想告诉你，点是从0开始编号的，你这样数据就是错的，如果改成8，下面的程序照样对。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define pii pair<int, int> #define mk make_pair const int N = 1005; const int INF = 0x3f3f3f3f; int g[N][N], pre[N], n; int path(int s, int t) { int lowc[N];//lowc[i]表示以i为终点的压入量 bool vis[N]; priority_queue<pii> q;//当前容量大的边（或者说是点）被放在队首 memset(vis, false, sizeof(vis)); memset(pre, -1, sizeof(pre)); memset(lowc, 63, sizeof(lowc)); q.push(make_pair(INF, s)); while(!q.empty()) { int u = q.top().second; q.pop(); if(u == t)//如果到达汇点，因为每次处理的都是容量最大的路，所以返回 return lowc[t]; if(vis[u]) continue; vis[u] = true; for(int i = 0; i < n; i++) if(!vis[i] && g[u][i] > 0) { if(lowc[i] == INF) lowc[i] = min(lowc[u], g[u][i]); else { if(g[u][i] < lowc[u]) lowc[i] = max(lowc[i], g[u][i]); else lowc[i] = lowc[u]; } pre[i] = u;//记录路径 q.push(mk(lowc[i], i)); } } return 0; } void maxFlow(int s, int t) { int first = 1, maxflow = 0, flow, minc = INF; while(true) { flow = path(s, t);//每次获得一条流量最大的路（注意是一条路） if(flow == 0) break; if(first) { minc = flow; first = 0; } maxflow += flow; for(int i = t; i != s; i = pre[i]) { g[pre[i]][i] -= flow; g[i][pre[i]] += flow; } } printf("%.3f\n", maxflow*1.0 / minc); } int main() { int T, kase, e, u, v, w, a, b; scanf("%d", &T); while(T--) { scanf("%d%d%d%d%d", &kase, &n, &e, &a, &b); memset(g, 0, sizeof(g)); while(e--) { scanf("%d%d%d", &u, &v, &w); g[u][v] += w;//两点之间的容量都加上 } printf("%d ", kase); maxFlow(a, b); } return 0; }