模板題鏈接：點我點我:-)
以前一直寫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);新聞熱點
疑難解答
