Tata: Created page with "Max Flow imprement with scaling algorithm O(nmlgU) #include #include #include #define INF 2000000000 using namespace std; struct Edge { i..."

2019-03-07T17:15:06Z

Created page with "Max Flow imprement with scaling algorithm O(nmlgU) #include<stdio.h> #include<algorithm> #include<vector> #define INF 2000000000 using namespace std; struct Edge { i..."

New page

Max Flow imprement with scaling algorithm O(nmlgU)

#include<stdio.h>
#include<algorithm>
#include<vector>
#define INF 2000000000
using namespace std;
struct Edge
{
int v,w,u;
};
vector<Edge*> E[1005];
int ch[1005];
Edge *root;
int T;
bool dfs(int x,int lt,int k)
{
int a;
if(x==lt)
return 1;
ch[x]=T;
for(a=0;a<E[x].size();a++)
if(ch[E[x][a]->w]!=T && E[x][a]->u>=k)
if(dfs(E[x][a]->w,lt,k))
{
E[x][a]->u-=k;
if((E[x][a]-root)%2)
root[E[x][a]-root-1].u+=k;
else
root[E[x][a]-root+1].u+=k;
return 1;
}
return 0;
}
int maxflow(int n,int m,int s,int t,Edge *edges,int *f)
{
int a,k=0;
bool tmp;
root=edges;
for(a=0;a<m;a++)
{
E[edges[a].v].push_back(&edges[a]);
f[a]=edges[a].u;
if(k<f[a]) k=f[a];
}
for(T=1;k>0;T++)
if(!dfs(s,t,k))
k/=2; //maxflow ver. scaling algor O(nmlgU)
for(a=0;a<m;a++)
f[a]-=edges[a].u;
for(a=0,k=0;a<E[t].size();a++)
k+=E[t][a]->u;
return k;
}

Max Flow - Revision history

Tata: Created page with "Max Flow imprement with scaling algorithm O(nmlgU) #include #include #include #define INF 2000000000 using namespace std; struct Edge { i..."