relabel-to-front.cpp

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

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <list>
using namespace std;
#define F(i,begin,end) for(i=end-1;i>=begin;i--)
const int maxn = 128;
const int INF = 1<<30;

struct Edge
{
    int u,v,cap,flow;
    Edge(int pu,int pv,int pcap){
        u=pu,v=pv,cap=pcap,flow=0;
    }
    int other(int pu){//返回这条边的另外一个顶点 
        return pu==u?v:u;
    }
    int capto(int pu){//返回指向pu的流量。注意正反向弧的情况 
        return pu==u?flow:cap-flow;
    }
    void addflow(int pu,int d){//修改增广路上的可行流 
        flow+=pu==v?d:-d;
    }
};

vector<Edge *>net[maxn]; //net[i]中包含i节点的正向弧和反向弧
vector<Edge> eg;//保存边集
int h[maxn];
int e[maxn];
int que[maxn+maxn];
int n,m,s,t;

void bfs()
{
    bool used[maxn];
    int front,rear,ed,now,i,v;
    memset(used,false,sizeof(used));
    memset(h,0,sizeof(h));
    int cnt=0;
    front = rear =0;
    que[rear]=t;
    while(front<rear){
        cnt++;
        ed=rear;
        while(front<=ed){
            now=que[front];
            F(i,0,net[now].size()){
                v=net[now][i]->other(now);
                if(!used[v]){
                     used[v]=true;
                     ++rear;
                     que[rear]=v;
                     h[v]=cnt;
                }
            }
            front++;
        }
    }
    h[s]=t;
} 

// 初始化流量，把与s相连的流都压满 
void initflow()
{
    int i,v;
    F(i,0,t+1)e[i]=0;
    F(i,0,net[s].size()){
        net[s][i]->flow=net[s][i]->cap;
        v=net[s][i]->other(s);
        e[v]+=net[s][i]->flow;
        e[s]-=net[s][i]->flow;
    }
    bfs();
}

//重标号
void relabel(int u)
{
    int i,v,min,cap;
    min=INF;
    F(i,0,net[u].size()){
        v=net[u][i]->other(u);
        cap=net[u][i]->capto(v);
        if(cap>0 && h[v]<min) min=h[v];
    }
    h[u]=min+1;
} 

//discharge 处理有余流的节点
void discharge(int u)
{
    int i,v,p;
    i=net[u].size()-1;
    while(e[u]>0){
        if(i>=0){
            v=net[u][i]->other(u);
            p=net[u][i]->capto(v);
            p=p<e[u]?p:e[u];
        }
        if(i<0){//余流没有压完 ，修改标号 
            relabel(u);
            i=net[u].size()-1;
        }
        else if(p>0 && h[u]==h[v]+1){
            e[u]-=p;
            e[v]+=p;
            net[u][i]->addflow(v,p);
        }
        else i--;
    }
} 

void preflow()
{
    list<int> list_flow;
    list<int>::iterator p;
    int u,i,old_height;
    initflow();
    p=list_flow.begin();
    F(i,0,t+1)
        if(i!=s && i!=t)list_flow.insert(p,i);
    p=list_flow.begin();
    while(p!=list_flow.end()){//重标号后要提前
        u=*p;
        old_height=h[u];
        discharge(u);
        if(h[u]>old_height){
            list_flow.erase(p);
            list_flow.insert(list_flow.begin(),u);
            p=list_flow.begin();
        }
        p++;
    }
}