ISAP 網(wǎng)絡(luò)流模板

2019-11-11 01:33:30

字體：大中小

供稿：網(wǎng)友

模板題鏈接：點(diǎn)我點(diǎn)我:-)

以前一直寫(xiě)Dinic的，發(fā)現(xiàn)神奇的isap又短又快，然后。。Dinic轉(zhuǎn)isap吧！！！注意：那個(gè)e.flow>0一定要寫(xiě)的，不然，沒(méi)有這條邊還遞歸，會(huì)對(duì)d數(shù)組造成影響！

原理大概是把原來(lái)的Dinic的dfs與bfs合并了！現(xiàn)在的d[i]表示的是到匯點(diǎn)的最少步數(shù)，然后當(dāng)i的路增廣完了以后，它肯定不存在原來(lái)的步數(shù)可以增廣了，那么讓d[i]++即可。 gap[i]表示步數(shù)為i的點(diǎn)有多少個(gè)

//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; //這里是因?yàn)間ap[d[now]]沒(méi)有的話(huà)，now無(wú)法從上層（它要加一了）增廣過(guò)來(lái)（路斷掉了），直接無(wú)解了 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);