最大ストリームC++実装


#include 
#include 

using namespace std;

#define VERTEX 7 //     
#define UINT_MAX 0xFFFF
// 
/
//        S   A   B   C   D   E   T
//	  S   0   3   1   0   0   0   0 
//    A   0   0   0   3   0   0   0
//    B   0   0   0   5   4   0   0
//    C   0   0   0   0   0   0   2  
//	  D   0   0   0   0   0   2   0
//	  E   0   0   0   0   0   0   3
//	  T   0   0   0   0   0   0   0


//    
int capacity[VERTEX][VERTEX];

//     
bool visited[VERTEX];

//      
int from[VERTEX];

//    
int min(int x,int y){
	return x q;

	q.push(0);
	
	visited[0] = true;

	init_from();

	//        
	
	while(q.empty()==false){
		where = q.front();
		q.pop();
		for(next=0;next0){
				q.push(next);
				visited[next] = true;
				from[next] = where;
				if(next==VERTEX-1)
					goto now;//exit while
			}
		}
	}
now:
	//           
	where = VERTEX-1;
	path_cap = UINT_MAX;
	while(from[where]>-1){
		//    
		prev = from[where];
		path_cap = min(path_cap,capacity[prev][where]);
		where = prev;
	}

	//           path_cap UINT_MAX
	if(path_cap == UINT_MAX)
		return 0;
	else return path_cap;
}

//     
int max_flow(){
	//   
	int result = 0;
	//       
	int path_capacity=0;

	while(true){
		//find_path            ,  0     
		path_capacity=find_path();
		if(path_capacity==0){
			break;
		}else{
			result += path_capacity;
		}
	}

	return result;
}

void main(){
	init_capacity();
	init_visited();
	printf("%d
",max_flow()); return; }
#include 
#include 
#include 

using namespace std;

#define VERTEX 7 //     
#define UINT_MAX 0xFFFF
//    
int capacity[VERTEX][VERTEX];

//     
bool visited[VERTEX];

//      
int from[VERTEX];

typedef struct NODE{
	int vertex;
	int priority;
	int from;//      
}node,*pnode;

//    
int min(int x,int y){
	return xvertex = vertex;
	n->priority = priority;
	n->from = from;
	return n;
}

//priority-first search (PFS)
int find_path(){
	int where,cost;
	int new_cost;
	int path_cap;
	int next;
	int prev;//    

	priority_queue pq;
	pq.push(init_node(0,UINT_MAX,-1));
	init_from();
	path_cap = 0;
	while(pq.empty()==false){
		pnode aux = pq.top();
		pq.pop();
		where = aux->vertex;
		cost = aux->priority;
		if(visited[where]) continue;
		from[where] = aux->from;
		if(where == VERTEX-1){
			path_cap = cost;
			break;
		}
		visited[where] = true;
		for(next=0;next0){
				new_cost = min(cost,capacity[where][next]);
				pq.push(init_node(next,new_cost,where));
			}
		}
	}
	//      
	where = VERTEX-1;
	while(from[where]>-1){
		prev = from[where];
		capacity[prev][where] -= path_cap;
		capacity[where][prev] += path_cap;
		where = prev;
	}
	return path_cap;
}

//     
int max_flow(){
	//   
	int result = 0;
	//       
	int path_capacity=0;

	while(true){
		//find_path            ,  0     
		path_capacity=find_path();
		if(path_capacity==0){
			break;
		}else{
			result += path_capacity;
		}
	}

	return result;
}

void main(){
	init_capacity();
	init_visited();
	printf("%d
",max_flow()); return; }

参照先:http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow