怒搞一下午網(wǎng)絡(luò)流，又去我一塊心病。

從2F到SAP再到Dinic最終過(guò)掉了。

但是書上說(shuō)Dinic的時(shí)間復(fù)雜度為v*v*e。感覺也應(yīng)該超時(shí)的啊，但是過(guò)掉了，好詭異。

后兩種算法都是在第一種的基礎(chǔ)上進(jìn)行優(yōu)化。

第一種方法就是不停的尋找增廣路。后兩種引進(jìn)了層次網(wǎng)絡(luò)的概念。第三種又改善了尋找增廣路的方法。

如今僅僅能理解到這里了。。

。

#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map>#pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 6000007using namespace std;struct E {int u,v,Max,now,next; }edge[30000];int Top;int head[300];void Link(int u,int v,int w) {edge[Top].u = u;edge[Top].v = v;edge[Top].Max = w;edge[Top].now = 0;edge[Top].next = head[u];head[u] = Top++; }struct P {int pre,now,floor;bool mark; }sta[300];void Modify(int a,int t) {while(t != 1){edge[sta[t].pre].now += a;t = edge[sta[t].pre].u;} }int SAP(int s,int t,int n) {for(int i = 1;i <= n; ++i)sta[i].mark = false;queue<int> q;q.push(s);sta[s].mark = true;sta[s].now = 2000000000;sta[s].pre = -1;while(q.empty() == false){if(sta[t].mark && sta[t].now){Modify(sta[t].now,t);return sta[t].now;}int f = q.front();q.pop();for(int p = head[f];p != -1; p = edge[p].next){if(sta[edge[p].v].mark == false && sta[edge[p].u].floor == sta[edge[p].v].floor-1 && sta[edge[p].u].floor < sta[t].floor){sta[edge[p].v].now = min(sta[f].now,edge[p].Max - edge[p].now);if(sta[edge[p].v].now == 0)continue;sta[edge[p].v].pre = p;//記錄邊的存儲(chǔ)位置sta[edge[p].v].mark = true;q.push(edge[p].v);}}}return 0; }void Updata_Floor(int s,int t,int n) {queue<int> q;for(int i = 0;i <= n; ++i)sta[i].mark = false,sta[i].floor = n;q.push(s);sta[s].mark = true;sta[s].floor = 1;while(q.empty() == false){int f = q.front();q.pop();if(sta[t].mark && sta[t].floor <= sta[f].floor)return ;for(int p = head[f];p != -1; p = edge[p].next){if(sta[edge[p].v].mark == false && edge[p].now < edge[p].Max){sta[edge[p].v].mark = true;sta[edge[p].v].floor = sta[f].floor + 1;q.push(edge[p].v);}}} }int dfs(int s,int t,int a) {if(s == t)return a;int f = 0;for(int p = head[s],temp = 0;p != -1; p = edge[p].next){if((sta[edge[p].v].floor < sta[t].floor || edge[p].v == t) && sta[edge[p].v].floor == sta[s].floor+1 && edge[p].now < edge[p].Max){temp = dfs(edge[p].v,t,min(a-f,edge[p].Max-edge[p].now));edge[p].now += temp;f += temp;}}return f; }int Dinic(int s,int t,int n) {return dfs(s,t,200000000); }int Cal_Max_Flow(int s,int t,int n) {int temp,f = 0;do{Updata_Floor(s,t,n);//temp = SAP(s,t,n);temp = Dinic(s,t,n);f += temp;}while(temp);return f; }int main() {char s[50];int i,n,np,nc,m,u,v,w;while(scanf("%d %d %d %d",&n,&np,&nc,&m) != EOF){memset(head,-1,sizeof(head));Top = 0;for(i = 0;i < m; ++i){scanf("%s",s);sscanf(s,"(%d,%d)%d",&u,&v,&w);Link(u+2,v+2,w);}for(i = 0;i < np; ++i){scanf("%s",s);sscanf(s,"(%d)%d",&u,&w);Link(1,u+2,w);}for(i = 0;i < nc; ++i){scanf("%s",s);sscanf(s,"(%d)%d",&u,&w);Link(u+2,n+2,w);}printf("%d\n",Cal_Max_Flow(1,n+2,n+2));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/mqxnongmin/p/10966684.html

總結(jié)

以上是生活随笔為你收集整理的初涉网络流 POJ 1459 Power Network的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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