» » Maximum Flow (basic)

Maximum Flow (basic)

   7:58 PM       

 
vector < int > M[mx];
int pre[mx], cap[mx][mx];
bool color[mx];
int bfs(int s, int t){
	int ok,u,v,sz,i,path_cap;
	memset(pre,-1,sizeof(pre));
	memset(color,0,sizeof(color));
	queue < int > q;
	
	color[s] = 1;
	q.push(s);
	ok = 1;
	while(!q.empty() && ok){
		u = q.front();
		q.pop();
		sz = M[u].size();
		for(i=0;i<sz;i++){
			v = M[u][i];
			if(!color[v] && cap[u][v] > 0){
				q.push(v);
				color[v] = 1;
				pre[v] = u;
				if(v==t){ok = 0;break;}
			}
		}
	}
	path_cap = inf;
	u = t;
	while(pre[u]!=-1){
		v = pre[u];
		path_cap = _min(path_cap, cap[v][u]);
		u = v;
	}
	u = t;
	while(pre[u]!=-1){
		v = pre[u];
		cap[v][u] -= path_cap;
		cap[u][v] += path_cap;
		u = v;
	}
	if(path_cap==inf)return 0;
	return path_cap;
}

int max_flow(int s, int t){
	int r,pcap;
	r = 0;
	while(true){
		pcap = bfs(s,t);
		if(!pcap)break;
		r += pcap;
	}
	return r;
}