模板题链接：点我点我:-)
以前一直写Dinic的，发现神奇的isap又短又快，然后。。Dinic转isap吧！！！ 注意：那个e.flow>0一定要写的，不然，没有这条边还递归，会对d数组造成影响！
原理大概是把原来的Dinic的dfs与bfs合并了！现在的d[i]表示的是到汇点的最少步数，然后当i的路增广完了以后，它肯定不存在原来的步数可以增广了，那么让d[i]++即可。 gap[i]表示步数为i的点有多少个
//miaomiao 2017.2.7#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<vector>using namespace std;#define pb push_back#define Set(a, v) memset(a, v, sizeof(a))#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)#define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--)#define N (10000+5)#define INF 0x3f3f3f3fstruct Edge{ int to, flow;};int n, s, t, d[N], gap[N];vector<Edge> edges;vector<int> G[N];int isap(int now, int minf){ if(now==t) return minf; int f, ret = 0; For(i, 0, G[now].size()-1){ Edge &e = edges[G[now][i]]; if(d[now]==d[e.to]+1 && e.flow > 0 && (f=isap(e.to, min(minf, e.flow)))>0){ e.flow -= f; ret += f; edges[G[now][i]^1].flow += f; minf -= f; if(minf <= 0) return ret; } } if(!(--gap[d[now]])) d[s] = n; //这里是因为gap[d[now]]没有的话，now无法从上层（它要加一了）增广过来（路断掉了），直接无解了 gap[++d[now]]++; return ret;}int main(){#ifndef ONLINE_JUDGE freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);#endif int m, u, v, w, add, ans = 0; scanf("%d%d%d%d", &n, &m, &s, &t); For(i, 1, m){ scanf("%d%d%d", &u, &v, &w); edges.pb((Edge){v, w}); edges.pb((Edge){u, 0}); int tmp = edges.size(); G[u].pb(tmp-2); G[v].pb(tmp-1); } gap[0] = n; while(d[s] < n) ans += isap(s, INF); PRintf("%d/n", ans); return 0;}新闻热点
疑难解答
