虽然时间复杂度上看起来更优$O(n^2\sqrt{m})$,但是在随机图下,却没有ISAP快。
HLPP采用的也是分层图结构,不过它是实时流动,也就是实时更新分层图。
初始只有$s$的层次为$n$,其它待搜索,均为$0$
与ISAP相似的,如果一个点所携带的流量推不出去了,就改变它在分层图的层次,具体也就是在残存流量图中,与它相邻的点取最小的一个+1,就是它的层次。
同样可以使用Gap优化,来减少状态。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e4+5,M=12e4+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node
{
int x,d;
node(int x=0,int d=0):x(x),d(d){}
bool operator <(const node a)const{return d<a.d;}
};
struct heap
{
node a[M];int len;
void up(int j){for(int i=j>>1;j>1&&a[i]<a[j];j=i,i=j>>1)swap(a[i],a[j]);}
void down(int i)
{
for(int j=i<<1;j<=len;i=j,j=i<<1)
{
if(j<len&&a[j]<a[j+1])++j;
if(a[i]<a[j])swap(a[i],a[j]);
else break;
}
}
void push(node x){a[++len]=x;up(len);}
void pop(){a[1]=a[len--];down(1);}
bool size(){return len;}
node top(){return a[1];}
}q;
struct edge{int y,next;ll c;}a[M<<1];int last[N],len;
void ins(int x,int y,ll c)
{
a[++len]=(edge){y,last[x],c};last[x]=len;
a[++len]=(edge){x,last[y],0};last[y]=len;
}
ll prs[N];int s,t,n,m,d[N],gap[N];
bool push(int x,int y,int k)
{
ll tmp=min(a[k].c,prs[x]);
a[k].c-=tmp;a[k^1].c+=tmp;prs[x]-=tmp;prs[y]+=tmp;
return tmp;
}
void Gap(int l){for(int i=1;i<=n;i++)if(i!=s&&i!=t&&d[i]>l&&d[i]<=n)d[i]=n+1;}
ll maxflow()
{
memset(prs,0,sizeof(prs));memset(d,0,sizeof(d));memset(gap,0,sizeof(gap));
d[s]=n;prs[s]=1e12;q.push(node(s,d[s]));
while(q.size())
{
node now=q.top();q.pop();
int x=now.x;
if(!prs[x])continue;
for(int k=last[x],y=a[k].y;k;k=a[k].next,y=a[k].y)
if((x==s||d[x]==d[y]+1)&&push(x,y,k)&&y!=t&&y!=s)q.push(node(y,d[y]));
if(prs[x]&&x!=s&&x!=t)
{
if(!(--gap[d[x]]))Gap(d[x]);//加速结束
++gap[++d[x]];q.push(node(x,d[x]));
}
}
return prs[t];
}
int main()
{
len=1;
qr(n),qr(m);qr(s),qr(t);
for(int i=1,x,y,c;i<=m;i++)qr(x),qr(y),qr(c),ins(x,y,1ll*c);
qw(maxflow());puts("");
return 0;
}
最后一次更新于2020-03-23
0 条评论