网络最大流算法—最高标号预留推进HLPP

2018-01-13 07:55:21来源:cnblogs.com作者:自为风月马前卒人点击

代码

`#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<queue>using namespace std;const int MAXN=2*1e3+10;const int INF=1e8+10;inline char nc(){    static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){    char c=nc();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}    return x*f;}int N,M,S,T;int H[MAXN];//每个节点的高度int F[MAXN];//每个节点可以流出的流量int gap[MAXN];//每个高度的数量 struct node{    int u,v,flow,nxt;}edge[MAXN];int head[MAXN];int num=0;//注意这里num必须从0开始 inline void add_edge(int x,int y,int z){    edge[num].u=x;    edge[num].v=y;    edge[num].flow=z;    edge[num].nxt=head[x];    head[x]=num++;}inline void AddEdge(int x,int y,int z){    add_edge(x,y,z);    add_edge(y,x,0);//注意这里别忘了加反向边 }struct comp{    int pos,h;    comp(int pos=0,int h=0):pos(pos),h(h) {}    inline bool operator < (const comp &a) const {return h<a.h;} };priority_queue<comp>q;bool Work(int u,int v,int id){    int val=min(F[u],edge[id].flow);    edge[id].flow-=val;edge[id^1].flow+=val;    F[u]-=val;F[v]+=val;    return val;}inline int HLPP(){    H[S]=N;F[S]=INF;q.push(comp(S,H[S]));    while(q.size()!=0)    {        int p=q.top().pos;q.pop();        if(!F[p]) continue;        for(int i=head[p];i!=-1;i=edge[i].nxt)            if( (p==S||H[edge[i].v]+1==H[p]) && Work(p,edge[i].v,i) && edge[i].v!=S && edge[i].v!=T)                q.push( comp(edge[i].v,H[edge[i].v]) );        if(p!=S && p!=T && F[p])        {            if( (--gap[ H[p] ])==0 )//该高度不存在             {                for(int i=1;i<=N;i++)                    if( H[p]<H[i]&&H[i]<=N && p!=S && p!=T )                         H[i]=N+1;//设置为不可访问             }            ++gap[ ++H[p] ];//高度+1             q.push( comp(p,H[p]) );        }    }    return F[T];}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif     memset(head,-1,sizeof(head));    N=read(),M=read(),S=read(),T=read();    for(int i=1;i<=M;i++)    {        int x=read(),y=read(),z=read();        AddEdge(x,y,z);     }    printf("%d", HLPP() );     return 0;}`