#include <stdio.h> #include <string.h> const int inf=1<<30; #define MAXM 2000 struct edge {int from, to, val, next; }e[MAXM*MAXM];int v[MAXM]; int n,m,len,st,ed; //st = 源點(diǎn) ed = 匯點(diǎn)void init() {len = 0;memset(v,-1,sizeof(v)); }void insert(int from, int to, int va) { e[len].from = from, e[len].to = to; e[len].val = va; e[len].next = v[from];v[from] = len++; e[len].from = to, e[len].to = from; e[len].val = 0; e[len].next = v[to];v[to] = len++; } int sap() { int dist[MAXM],now[MAXM],cnt[MAXM],pre[MAXM],cur[MAXM];int tot_flow; int now_flow, found, min; int i, j, t; memset(dist, 0, sizeof(dist));memset(now, -1, sizeof(now)); memset(cnt, 0, sizeof(cnt)); i = st; tot_flow = 0; now_flow = inf; cnt[0] = n;while(dist[st] < n) { cur[i] = now_flow; found = 0; if(now[i] == -1) t = v[i]; else t = now[i]; while(t != -1) { j = e[t].to; if(e[t].val > 0 && dist[j] + 1 == dist[i]) { found = 1; now[i] = t; if(e[t].val < now_flow) now_flow = e[t].val; pre[j] = t; i = j; if(i == n+m+1) { tot_flow += now_flow; while(i != st) { e[pre[i]].val -= now_flow; e[pre[i]^1].val += now_flow; i = e[pre[i]].from; } now_flow = inf; } break; } t = e[t].next; } if(found) continue; if(--cnt[dist[i]] == 0) break; min = n - 1; t = v[i]; while(t != -1) { if(e[t].val > 0 && dist[e[t].to] < min) { min = dist[e[t].to]; now[i] = t; } t = e[t].next; } dist[i] = min + 1;cnt[dist[i]]++; if(i != st) { i = e[pre[i]].from; now_flow = cur[i]; } } return tot_flow; }int main() {int x,y,va;while (scanf("%d%d",&n,&m),n+m){init();st = 1;ed = n;while (m--){scanf("%d%d%d",&x,&y,&va);insert(x,y,va);}printf("%d/n",sap());}return 0; }
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的网络最大流（SAP）模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。