グーグー-HLPPアルゴリズム

hlppアルゴリズムまとめ
ふと見つけてしばらく(X)
emmはまず大体において、hlppはネットワークフローアルゴリズムに対して複雑度がより優れているアルゴリズムであり、プレストリーム推進(すなわちアナログ)複雑度に基づいて、上界はn 2ルートmであり、走れない.
(だからマスターしました.ほとんどのdinicで解決できる問題とほとんどのdinicで解決できない問題を解決できます.
まず以前のdinicアルゴリズムを放してください.
あなたの谷P 376ネットワーク最大ストリームテンプレート

#include
#define re register
using namespace std;
const int maxxx=(1ll<<31)-1;
inline int read()
{
    register int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct node
{
    int to,nxt,dis;
}e[210000];
int head[100010],cur[100010],cnt=-1;
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int d[100010],n,m,s,t;
bool bfs()
{
    queue<int> q;
    q.push(s);
    memset(d,-1,sizeof(d));
    d[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].nxt)
        {
            int v=e[i].to;
            if(e[i].dis && d[v]==-1)
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return (d[t]!=-1);
}
int dfs(int u,int flow)
{
    if(u==t) return flow;
    int tmp=0,newflow;
    for(int i=cur[u ];i!=-1;i=e[i].nxt)
    {
        int v=e[i].to;
        if(d[v]==d[u]+1 && e[i].dis)
        {
            newflow=dfs(v,min(flow,e[i].dis));
            flow-=newflow;
            e[i].dis-=newflow;
            tmp+=newflow;
            e[i^1].dis+=newflow;
            if(!flow) break;
        }
    }
    if(!tmp) d[u]=-1;
    return tmp;
}
void dinic()
{
    int maxflow=0;
    while(bfs())
    {
        for(re int i=1;i<=n;++i) cur[i]=head[i];
        maxflow+=dfs(s,maxxx);
    }
    printf("%d
",maxflow);
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read(); m=read(); s=read(); t=read();
    for(re int i=1;i<=m;++i)
    {
        int x,y,z;
        x=read(); y=read(); z=read();
        add(x,y,z); add(y,x,0);
    }
    dinic();
}

Dinicアルゴリズムの基本的な考え方は、成長路を探して、トラフィックを拡大するためのアルゴリズムです.そして、正しい性を保証するために、自分の後悔を逆にする機会を与えます.
(私達も模擬費用の流れの計算方法が分かりません.何ですか?
しかし、このHLPPアルゴリズムは、拡張アルゴリズムに基づくネットワークフローではなく、別の(欲張り?)アルゴリズムに基づいて、プリストリーム推進を行います.
(循環屁は二回目)
基本思想:
まず基本的な考えを言いましょう.このアルゴリズムは各点に一つの流量を格納することができます.ただし、最後にソース・ポイント以外の点がゼロになることを保証します.
したがって、各ノードによって格納されている超流動を押しのけることができるように、高度の概念を導入した(ますますシミュレーションのようになった).
同時に高さを導入すると、2つのノードが互いに超過流を押すことを避けることができる.
でも、なぜかというと、現実の生活の中の水たまりは、一例として、私達は超額の流れを低いノードにおしつけています.その結果、ある水流がこの水たまりにたまっています.周りが彼より高いので、かわいそうな水たまりです.
巨大な超過流に耐えながら、結局は押しても送れないので、私達は死ぬことにしました.
どうすればいいですか?このような点の高さを上げるべきです.
この操作はレッテルの張り替えといいます.
(一番上のマークとなんですか?全然できません.
具体的な実現過程:
私たちはe[i]を使って一つの点のオーバーフローを表し、h[i]は一つの点の高さを表します.
送金ポイントからbfsの割当高さが開始されます.ここではネットワークフローの階層図とは異なり、为替点に流れることができるように高度な増分が必要です.
各処理高さが最高で、かつ、オーバーフローが0でない点(優先キューでメンテナンス)については、プッシュフロー操作を行います.…
 
 
悪いとしても、また鴨に戻してもらえます.
だからアルゴリズムの正確性は一目瞭然です.拡張路の欲張りな反悔と同じです.
　   次にe[u]が0に等しくない場合は、ラベルを貼り直し、高さを上げて退廃を待ち続けます.
 最後に、もしソースポイントを除いて、その他のオーバーフローは全部0であるなら、方案が合法的であることを説明します.この時、送金ポイントのオーバーフローは元の図の最大フローです.
最適化:
この優れたアルゴリズムを実現するためには、増広路アルゴリズムよりも完全に優れています.船の新しい最適化に参加します.
GAP最適化
　 もう一つの点vがラベルを貼られた後、もし元の高さがもう他の点がないなら、それより高い点はきっとtに流れを押し戻すことができません.
したがって、h[v]以上の高さとn＋1以下の点の高さをn＋1に設定して、できるだけ早くsに流量を送ることができます.
この高さがすでに他のノードがないとどう判断するかについては、ISAPと同様に1つのgap配列でカウントすることができ、これがHLPPのgap最適化である.
具体的な実現:
　　

#include
#define re register
#define il inline
#define inc(i,j,k) for(re int i=j;i<=k;++i)
#define ra(i,u) for(re int i=head[u];i!=-1;i=a[i].nxt)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxm=120010;
const int maxn=2010;
struct node
{
    int to,nxt,flow;
}a[maxm<<1];
int head[maxn],gap[maxn],h[maxn],e[maxn];
bool vis[maxn];
int cnt=-1,n,m,st,ed;
struct cmp {il bool operator () (int x,int y)const{return h[x]<h[y];}};
priority_queue<int,vector<int>,cmp> pq;
queue<int> q;
il void add(int u,int v,int w)
{
    a[++cnt].to=v;
    a[cnt].nxt=head[u];
    a[cnt].flow=w;
    head[u]=cnt;
}
il bool bfs()
{
    memset(h,inf,sizeof(h));
    h[ed]=0;
    q.push(ed);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        ra(i,t)
        {
            int v=a[i].to;
            if(a[i^1].flow && h[v]>h[t]+1)
            {
                h[v]=h[t]+1;
                q.push(v);
            }
        }
    }
    return h[st]!=inf;
}
il void push(int u)
{
    ra(i,u)
    {
        int v=a[i].to;
        if((a[i].flow) && (h[v]+1==h[u]))
        {
            int df=min(e[u],a[i].flow);
            a[i].flow-=df;
            a[i^1].flow+=df;
            e[u]-=df;
            e[v]+=df;
            if((v!=st)&&(v!=ed)&&(!vis[v]))
            {
                pq.push(v);
                vis[v]=1;
            }
            if(!e[u])break;
        }
    }
}
il void relabel(int u)
{
    h[u]=inf;
    ra(i,u)
    {
        int v=a[i].to;
        if((a[i].flow)&&(h[v]+11;
    }
}
inline int hlpp()
{
    if(!bfs())return 0;
    h[st]=n;
    memset(gap,0,sizeof(gap));
    inc(i,1,n) if(h[i]!=inf)gap[h[i]]++;
    ra(i,st)
    {
        int v=a[i].to;
        if(int f=a[i].flow)
        {
            a[i].flow-=f;a[i^1].flow+=f;
            e[st]-=f;e[v]+=f;
            if(v!=st&&v!=ed&&!vis[v])
            {
                pq.push(v);
                vis[v]=1;
            }
        }
    }
    while(!pq.empty())
    {
        int t=pq.top();pq.pop();
        vis[t]=0;push(t);
        if(e[t])
        {
            gap[h[t]]--;
            if(!gap[h[t]])
            {
                inc(v,1,n)
                {
                    if(v!=st&&v!=ed&&h[v]>h[t]&&h[v]1)
                    {
                        h[v]=n+1;
                    }
                }
            }
            relabel(t);gap[h[t]]++;
            pq.push(t);vis[t]=1;
        }
    }
    return e[ed];
}
signed main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    inc(i,1,m)
    {
        int x,y;
        ll f;
        scanf("%d%d%lld",&x,&y,&f);
        add(x,y,f);
        add(y,x,0);
    }
    ll maxf=hlpp();
    printf("%lld",maxf);
    return 0;
}

これは私が問題を解いて少しずつ書いたのです.例題は後で書きます.
最大ストリーム——プレストリーム推進