最大ストリーム問題プリフロー推進アルゴリズム(BFS最適化)
4183 ワード
/*
Name:
Copyright:
Author:
Date: 14-06-17 09:26
Description: , :
BFS ,
, .
*/
#include
#include
using namespace std;
typedef struct VertexNode{ //
int num; //
struct VertexNode *next; // ,
} VertexNode;
const int MAXV=2000; //
const int MAXE=2000; //
const int INFINITY = 0x7fffffff; //
int capacity[MAXV][MAXV]; //
int flow[MAXV]; //
int dis[MAXV]; //
VertexNode *head; //
int MaxFlow_relabel_to_front(int src, int des, int n) ;
bool BFS(int src, int des, int n); //
void Check(int u, int n); // u , 0
int main()
{
int m, n, u, v;
ifstream fcin("maxflow.txt");
if (!fcin.is_open())
{
cout << "Error opening file"; exit (1);
}
fcin >> n >> m;
for(int i=0; i> u >> v;
fcin >> capacity[u][v];
}
cout << n << " " << m << endl;
for (int i=0; i 0)
{
// u relabel
bool relabel = true;
for (int v=0; v 0) // ,
{
relabel = false;
minFlow = (flow[u] < capacity[u][v]) ? flow[u] : capacity[u][v];
flow[u] -= minFlow;
flow[v] += minFlow;
capacity[u][v] -= minFlow;
capacity[v][u] += minFlow;
printf("push %d --%d--> %d, e[%d] = %d
", u, minFlow, v, u, flow[u]);
if (flow[u] == 0)
{
break;
}
}
}
// push , relabel
if (relabel)
{
minLevel = INFINITY;
for (int v=0; v 0 && minLevel > dis[v]) //
{
minLevel = dis[v];
}
}
dis[u] = minLevel + 1;
printf("relabel %d height to %d
", u, dis[u]);
}
}
}
int MaxFlow_relabel_to_front(int src, int des, int n)
{
int u, v, oldLevel, minFlow;
VertexNode *p = head;
if (BFS(src, des, n))//
{
dis[src] = n; // n
for (v = 0; v < n; v++) //
{
if (capacity[src][v] > 0) //
{
flow[src] -= capacity[src][v];
flow[v] = capacity[src][v];
capacity[v][src] = capacity[src][v];
capacity[src][v] = 0;
}
}
VertexNode *pre = head;
while (pre->next)
{
u = pre->next->num;
oldLevel = dis[u];
Check(u, n);
if (oldLevel < dis[u])// ,
{
p = pre->next;
pre->next = p->next; // p
p->next = head->next;// p
head->next = p;
pre = head;
}
pre = pre->next; //
}
}
p = head->next;
while (p)
{
delete head;
head = p;
p = head->next;
}
return flow[des];
}
bool BFS(int src, int des, int n)// , , false
{
int Queue[MAXV]; //
int v, front = 0, rear = 0; //
for(int i=0; inext = NULL;
for (front = 1; front < rear; front++)//
{
if (Queue[front] != src)
{
s = new VertexNode;
s->num = Queue[front];
s->next = head->next;
head->next = s;
}
}
return true;
}