//Program HighestLablePreflowPush;HLPP

// 較快的網絡流算法

//最高標號預留與推進算法

//記錄d值，然后優先處理d值較高的，直至沒有盈余。

// poj1459 Power Network

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#define maxn 105

#define max? 210

using namespace std;

?

typedef struct node

{

???? int num;

???? int a[maxn];

}node;

?

int n,s,t,maxflow;

int map[maxn][maxn];??????? //邊容量矩陣

int edge[maxn][maxn];?????? //鄰接矩陣

int cur[maxn],d[maxn],e[maxn];

struct node list[2*maxn-1];

int flag;

?

void pagheuristic();

void insert(int level,int x)//加入標號為level的節點x

{??? int num;

???? list[level].num++;

???? num = list[level].num;

???? list[level].a[num] = x;

}

void BFS()//精確計算距離標號dijkstra 建層次表

{

???? int p,q;int x[maxn];int i;

???? fill(d,d+maxn,max);

???? x[1] = t; d[t] = 0; q = 1; p = 0;

???? while(p<q)

???? {

???????? p++;

???????? for(i = 1; i <= edge[x[p]][0]; i++)

????????????? if(d[ edge[x[p]][i] ] == max){

?????????????????? q++;

?????????????????? x[q] = edge[x[p]][i];

?????????????????? d[x[q]] = d[x[p]] + 1;

?????????????????? if(x[q] != s) insert(d[x[q]],x[q]);

????????????? }

???? }

???? d[s] = n;

}

void push(int a,int b)

{

???? int x;

???? if(map[a][b] > e[a]) x = e[a];

???? else x = map[a][b];

???? map[a][b] -= x;

???? map[b][a] += x;

???? e[a] -= x;

???? e[b] += x;

}

void relabel(int a)

{

???? int i,min = max;

???? for(i = 1; i <= edge[a][0]; i++)

???????? if(map[a][edge[a][i]] > 0 && d[edge[a][i]] < min)

????????????? min = d[edge[a][i]];

???? d[a] = min + 1;

???? if(flag++ % n == 0) pagheuristic(); //此處加優化

}

bool check(int a)//discharge

{??? bool chk = false;

???? while(e[a] > 0)

???? {

???????? if(cur[a] > edge[a][0]){

????????????? relabel(a); chk = true; cur[a] = 1;

???????? }

???????? else if(map[a][ edge[a][cur[a]] ] > 0 && d[a] == d[ edge[a][cur[a]] ] + 1)

????????????? push(a,edge[a][cur[a]]);//j = edge[a][cur[a]] -> b是a第j 個鄰接點

???????? else cur[a]++;

???? }

???? return chk;

}

void update(int level)//將所有標號在level上的點拋上九天,會不會就是pagheuristic

{

???? int j,k;

???? for(j = level+1; j <= n; j++){

???????? for(k = 1; k <= list[j].num; k++){

????????????? list[n+1].a[list[n+1].num + k] = list[j].a[k];

????????????? d[list[j].a[k]] = n+1;

???????? }

???????? list[n+1].num += list[j].num;

???????? list[j].num = 0;

???? }

}

void HLPP()

{???

???? int i,b,level;

???? fill(e,e+maxn,0);

???? for(i = 1; i <= edge[s][0]; i++){//將所有s出發的弧充滿

???????? b = edge[s][i];

???????? e[b] = map[s][b];

???????? e[s] -= map[s][b];

???????? map[b][s] = e[b];

???????? map[s][b] = 0;

???? }

???? level = n;flag = 0;

???? while(level)

???? {

???????? level--;

???????? for(i = list[level].num; i >= 1; i--){

????????????? int a = list[level].a[i]; int num = list[level].num;

????????????? if(check(a)){??????????????????????????????????????????????? //如果有被重標記

?????????????????? if(level > 0 &&? list[level].num == 1) update(level);//免除把余流送回S的操作,該層只剩下一個點將要斷層才可update，因為在層次圖中如果斷層，則斷層上的頂點有留流，它必流回S，這時不用再計算，把它上放到n+1 層上去

?????????????????? insert(d[a],a);?????????????????????????????????????????????????

?????????????????? list[level].a[i] = list[level].a[num];????????????????? //有標記過則排除該點，把后面沒標記的移到前面來

?????????????????? list[level].num--;

?????????????????? level = d[a];?????????????????????????????????????????? //level 回升

???? ????????????? break;?????????????????????????????????????????????????????? //從新的最高level重新開始

????????????? }

???????? }

???? }

}

int main()

{??? void input(int node,int np,int nc,int m);

???? void init();

???? int node,np,nc,m;

???? while(scanf("%d%d%d%d",&node,&np,&nc,&m)==4)

???? {

???????? input(node,np,nc,m);

???????? init();

???????? BFS();

???????? HLPP();

???????? maxflow = e[t];

???????? printf("%d/n",maxflow);

???? }

???? return 0;

}

void init()

{

???? int i,j;

???? memset(edge,0,sizeof edge);

???? for(i = 0; i < n; i++)

???????? for(j = i+1; j <= n; j++)

????????????? if(map[i][j]||map[j][i]){//建立鄰接矩陣

?????????????????? edge[i][0]++;

?????????????????? edge[j][0]++;

?????????????????? edge[i][edge[i][0]] = j;

?????????????????? edge[j][edge[j][0]] = i;

????????????? }

???? fill(cur,cur+maxn,1);

???? for(i = 0; i <= n+1; i++) list[i].num = 0;

}

void input(int node,int np,int nc,int m)//complete map,mark s t n

{??? int a,b,cap;int i;

???? n = node+1;

???? s = 0; t = node+1; maxflow = 0;

???? fill(map[0],map[maxn],0);

???? for (i = 0 ; i < m? ;i++)

???? {

???????? while(getchar()!='(');

???????? scanf("%d,%d)%d",&a,&b,&cap);

???????? map[a+1][b+1] = cap;

???? }

???? for (i = 0 ; i < np ; i++)

???? {

???????? while(getchar()!='(');

???????? scanf("%d)%d",&b,&cap);

???????? map[s][b+1] = cap;

???? }

???? for (i = 0 ; i < nc ; i++)

???? {

???????? while(getchar()!='(');

???????? scanf("%d)%d",&b,&cap);

???????? map[b+1][t] = cap;

???? }

}

//距離標號法與重標記與前移算法容易退化，所以加一個優化pagheuristic——若存在某一個k(k<n)，

//沒有距離標號為k的點，則可以將標號為k--n的所有點移到標號為n+1，以此來提高效率。

//這個優化在relable時可以使用，為了節省時間，可以選在每k*n次檢查一次。

void pagheuristic()

{

???? int count[maxn*2];

???? int i,j;

???? fill(count,count+2*maxn,0);

???? for(i = 1; i <= n; i++) count[d[i]]++;

???? j = 1;

???? while(j < n && count[j] != 0) j++;

???? if(j == n) return;

???? for(i = 1; i <= n; i++)

???????? if(i != s && d[i] > j && d[i] <= n)

????????????? d[i] = n+1;

}

?

//http://billylinux.blog.hexun.com/16441424_d.html

//來自以上網址的翻譯

總結

以上是生活随笔為你收集整理的最高标号预留与推进算法 --- 就是要比 Dinic 快!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。