pfs.cpp

这是关于图论算法里面的一些代码,图论基本的思想代码的实现

/*BFS的变种：PFS -最大容量增广路径实现
 *效率较高 建议使用 
 */
const int MaxVertex = 410;   //最大节点数   
struct Node 
{   int v, wt; 
    Node(int vv=0, int ww=0) : v(vv), wt(ww) {} 
};   
int cap[MaxVertex][MaxVertex];      //边容量矩阵,若无边，则为0 
int flow[MaxVertex][MaxVertex];     //流矩阵  
int V;                              //图结点个数 
int maxflow;                        //最大流值 
int s, t;                           //源点，汇点 
int father[MaxVertex];              //记录增广路径用 

//*********************************************************
int MaxFlow(int ss, int tt); 
bool pfs(); 
void augment(int, int);
bool cmp(const Node&, const Node&);
//****************************************************


int MaxFlow(int ss, int tt) 
{ 
    s = ss, t = tt; 
    memset(flow, 0, sizeof(flow)); 
    maxflow = 0; 
    while(pfs()) 
        augment(s, t); 
    return maxflow; 
} 

bool cmp(const Node &a, const Node &b) 
{ 
    return a.wt < b.wt; 
}    
bool pfs() 
{ 
    int v, j, ww, x; 
    bool caled[MaxVertex];              
    int wt[MaxVertex];   //记录该节点所在的增广路上所容许通过的最大容量               
    vector<Node> myheap; 
    memset(father, 0xff, sizeof(int)*V);  
    memset(caled, 0, sizeof(bool)*V); 
    memset(wt, 0xff, sizeof(int)*V);      
    myheap.clear(); 
    father[s] = s; 
    myheap.push_back(Node(s, INT_MAX)); 
    // assert(s != t); 
    while(!myheap.empty())   //宽搜找增广路 
    { 
        v = myheap[0].v; ww = myheap[0].wt; 
        pop_heap(myheap.begin(), myheap.end(), cmp); //移除第一个顶点，并按cmp的顺序重新构造堆 
        myheap.pop_back(); //myheap.end()应该减一 
        if(caled[v]) continue; 
        caled[v] = 1; 
        for(j = 0; j < V; ++j) 
            if(cap[v][j]>0 && !caled[j]) 
            { 
                x = ww<cap[v][j] ? ww : cap[v][j]; 
                if(x <= wt[j]) continue; //有可能j点的增广路可由其他点到达，比较是不是比以前的大 最大容量增广路 
                father[j] = v;           //记录前驱节点 
                if(j == t) return 1; //找到可可扩充路径 
                wt[j] = x;  //可扩充容量 
                myheap.push_back(Node(j, x)); 
                push_heap(myheap.begin(), myheap.end(), cmp); //重新给堆排序，按照cmp 
            }    
    }    
    return 0; 
}        

void augment(int ss, int tt) 
{ 
    int tiny(INT_MAX); 
    int v(tt), w(father[v]); 
    do{ 
        if(tiny > cap[w][v]) tiny = cap[w][v]; 
        v = w, w = father[v]; 
    }while(v != ss);    
    v = tt, w = father[v]; 
    do{ 
        flow[w][v] += tiny; 
        flow[v][w] -= tiny; 
        cap[w][v] -= tiny; 
        cap[v][w] += tiny; 
        v = w, w = father[v]; 
    }while(v != ss); 
    maxflow += tiny;    
}