最大流EK和Dinic算法

EK算法

最朴素的求最大流的算法。 做法：不停的寻找增广路，直到找不到为止

代码如下：

@Frosero #include <cstdio> #include <iostream> #include <cstring> #include <queue> #define INF 0x3f3f3f3f using 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 0x3f3f3f3f using 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