最大ストリーム問題プリフロー推進アルゴリズム(BFS最適化)


/*
  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; }