学完了isap,感觉心情舒畅,毕竟isap比dinic好一点。
说到底isap其实是dinic(不熟悉dinic的人去我的博客找猴子课堂—-最大流与最小割(看看思想),已经置顶)优化版,熟悉的人知道dinic是通过不断分层来做的,但是,我们如果用打标记(貂蝉的标记)的方法就会快一些!
会快的原因就是因为他省了很多分层的时间,使得他比dinic要快不少,首先,我们先初始化一遍(从t开始搜,建个分层图(不是说不用宽搜了吗)),虽然过程中不用多次分层,但初始化分层,使得代码要干的事情少了不少(因为让代码通过自身调整标记要o(n^2)时间,但如果用宽搜初始化分层就让时间缩短为o(n),也是十分不错的呢!)
然后每次按分层规矩(注意,这里以结尾为原点建分层图,是由高的层流向比他低一层的层)找一条路径(没错,你没听错,就是单路增广!),从起点出发:
流完后,然后回到起点,找另外一条流完,就结束了?
比如这张:
下面一条可行路径就因为———(儿童不宜)的关系流不过去了(分层有时会导致两个相邻点层数相同)。。。
所以,isap的精华!出来吧!
询问?询问什么?就是找与他相连的点(边要有流量)中层数最小的,之后,它就可以变身成比这个编号大一层的点,继续为流量做贡献!(在一个点找不到下一个点时,就调整这个点的标记)
改完之后:
就这样解决了呢!(只需要在s的层数大于点数就可以退出了)
呵呵
上代码:
不!不!不!太慢了!
我们会发现一件事,如果一种数字的编号消失,就永远消失了,如果消失,路径少一编号就不行了,也可以退出!(可以用num记录每一编号的个数,在每次调整标记时判断)
耶!一顿操作猛如虎!(这叫断层优化)
证明(断层优化):
设当前编号为x的数没了,设y=x-1,那么,编号为y的点有没有可能变为x呢?首先,如果经过了x,那么s的层数≥x,且这个为最短的路径,也就说后面的s的编号都≥x,那么每条路经中必须有个x。
但x没了,也就需要一些点来与y的点连接变成x,但是,如果有的话,这些点的层数在作分层时,就已经等于x了(想想看,为什么不可能小于x(其实就是懒得写)),那么路径就不会产生断层(矛盾)!
所以断层优化成立,但是必须基于编号最小的基础上!
讲得好烂。。。
然后,上!代码。。。
include
include
include
using namespace std;
struct node
{
int y,c,next,other;
}a[210000];int len,last[210000],n,m,st,ed;
void ins(int x,int y,int c)
{
len++;
a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
len++;
a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;
a[len].other=len-1;a[len-1].other=len;
}//建边
int h[210000]/层数/,num[210000]/断层优化/,cur[210000]/弧优化/,qian[210000]/保留前一个点到达这里的边的编号/;
int list[210000],head,tail;
void bt()
{
head=1;tail=2;num[h[ed]=1]++;list[head]=ed;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y,kl=a[k].other;
if(a[kl].c>0 && h[y]==0)
{
num[h[y]=h[x]+1]++;
list[tail++]=y;
}
}
head++;
}
if(h[st]==0)h[st]=n+1;/判断能不能到达终点/
}
int mymin(int x,int y){return x<y?x:y;}
int add()/流量/
{
int now=ed,ans=999999999;
while(now!=st)
{
ans=mymin(ans,a[qian[now]].c);
now=a[a[qian[now]].other].y;
}/找路径上的最小流量/
now=ed;
while(now!=st)
{
a[qian[now]].c-=ans;a[a[qian[now]].other].c+=ans;
now=a[a[qian[now]].other].y;
}/减流/
return ans;
}
int findflow()
{
int ans=0,now=st;
bt();
while(h[st]<=n)
{
bool bk=true;
while(bk==true)/判断走不走得通/
{
bk=false;
for(int &k=cur[now];k;k=a[k].next)//想想这的当前弧为何长这样
{
int y=a[k].y;
if(a[k].c>0 && h[y]+1==h[now])
{
bk=true;
qian[y]=k;
now=y;
break;/记录/
}
}
if(now==ed)
{
ans+=add();now=st;
}/增值/
}
int minn=n;
for(int k=last[now];k;k=a[k].next)
{
if(a[k].c>0)minn=mymin(minn,h[a[k].y]);
}//找层数
if((–num[h[now]])==0)break;//断层优化
cur[now]=last[now];
num[h[now]=minn+1]++;//更改
if(now!=st)now=a[a[qian[now]].other].y;//想想为什么这样打(提示:从是不是最短的路径上想)
}
return ans;
}
int main()
{
scanf(“%d%d%d%d”,&n,&m,&st,&ed);
for(int i=1;i<=m;i++)
{
int x,y,c;scanf(“%d%d%d”,&x,&y,&c);
ins(x,y,c);
}
for(int i=1;i<=n;i++)cur[i]=last[i];
printf(“%dn”,findflow());
return 0;
}
为什么会快?
其实它比dinic少了很多没用的递归,让每次找路径都有作用,而且用标记省了bfs的时间,所以,只要不被恶意卡掉,isap整体上比dinic要优秀!
注:上面的图片侵权抱歉!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607624.html