最大ストリームC++実装
3618 ワード
#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