最大流EK和Dinic算法

EK算法

最樸素的求最大流的算法。
做法：不停的尋找增廣路，直到找不到為止

代碼如下：

@Frosero #include <cstdio> #include <iostream> #include <cstring> #include <queue> #define INF 0x3f3f3f3fusing namespace std; int n,m; int cap[202][202],flow[202][202],mf[202],pre[202];//cap為網絡的容量 flow為現在的流量 //mf[i]為原點到點i的最大流量 pre[i]為增廣路上i點上一個點int EK(int s,int t){memset(flow,0,sizeof(flow));queue<int>q;int ans = 0;while(1){while(!q.empty()) q.pop(); q.push(s);memset(mf,0,sizeof(mf));mf[1] = INF;while(!q.empty()){int u = q.front(); q.pop();for(int i=1;i<=m;i++)if(!mf[i] && flow[u][i] < cap[u][i]){pre[i] = u;q.push(i);mf[i] = min(mf[u],cap[u][i] - flow[u][i]);}}if(mf[t] == 0) break;ans += mf[t];for(int i=t;i!=s;i=pre[i]){flow[pre[i]][i] += mf[t];flow[i][pre[i]] -= mf[t];}}return ans; }int main(){while(scanf("%d %d",&n,&m)!=EOF){memset(cap,0,sizeof(cap));memset(flow,0,sizeof(flow));int u,v,w;while(n--){scanf("%d %d %d",&u,&v,&w);cap[u][v] += w;}printf("%d\n",EK(1,m));} }

Dinic算法

Dinic的優化部分就是給殘留網絡生成一個層次圖，然后盡量的利用層次圖后再形成新的層次圖。

理論上Dinic和EK算法的時間復雜度差不多，但是事實上Dinic算法要好得多。

代碼如下：

@Frosero #include <iostream> #include <cstdio> #include <queue> #include <cstring> #define INF 0x3f3f3f3fusing namespace std;int n,m,flow[202][202],cap[202][202]; int dis[202];//flow為現在的流量 cap為網絡的容量//dis為點的層次bool bfs(){ //形成層次圖memset(dis,-1,sizeof(dis));dis[1] = 0;queue<int>q; q.push(1);while(!q.empty()){int u = q.front(); q.pop();for(int i=1;i<=m;i++)if(dis[i] == -1 && flow[u][i] < cap[u][i]){dis[i] = dis[u] + 1;q.push(i);}}if(dis[m] == -1) return false;else return true; }int dfs(int s = 1,int f = INF){ //利用層次圖不斷尋找增廣路if(s == m || f == 0) return f;int ans = 0;for(int i=1;i<=m;i++)if(dis[i] == dis[s] + 1){int a = dfs(i,min(f,cap[s][i] - flow[s][i]));if(a == 0) continue;flow[s][i] += a;flow[i][s] -= a;ans += a;f -= a;if(f <= 0) break;}return ans; }int dinic(){ //Dinic主過程int ans = 0;while(bfs()){ans += dfs();}return ans; }int main(){while(scanf("%d %d",&n,&m)!=EOF){ //本代碼假設1為原點 m為匯點memset(flow,0,sizeof(flow));memset(cap,0,sizeof(cap));int u,v,w;while(n--){scanf("%d %d %d",&u,&v,&w);cap[u][v] += w;}printf("%d\n",dinic());}return 0; }

轉載于:https://www.cnblogs.com/ScratchingBear/p/5345837.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的最大流EK和Dinic算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。