注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

ISAP模板  

2014-02-03 22:54:40|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
-------------------------------------------------------------------------------------------
上次看到了WXR写的SAP的模板 真的太短了
刚好自己现在也在复习
(其实联赛后第一遍学网络流时也只做了5、6道题我会乱说?)
所以嘛 又把这个重写了一遍
不过还是好长啊QAQ
当然好懂就行
-------------------------------------------------------------------------------------------
///isap在EK的基础上主要有三种优化
///1 距离标号+gap
///2 当前弧
///3 瓶颈边(据说是借鉴dinic)
优化1是SAP与EK最根本的差别 也是效率提升最明显的
2、3加上后就是ISAP 不过这些都只是小小的优化
如果实现中额外的常数较大 2、3的优化就几乎看不出来了
然后由于距离标号的算法没有研究过 就不做评论了
当前弧应该是在每个点的邻接边的条数较多时有明显优化
瓶颈边应该是在路径较长时有明显优化
-------------------------------------------------------------------------------------------
void isap(int start,int aim,int node) ///start 为源点 aim为汇点 node为点的个数
{
    bfs(aim);///距离标号的预处理
    rep(i,node)
    cur[i]=firste[i];///当前弧先设定为第一条边
    int u=start,p;
    while(dist[start]<node)///不满足条件则一定出现gap
    {
        if(u==aim)
        {
            int mf=BIG;///mf为可以增大的流量
            for(p=pre[u];p;p=pre[v[p^1]])///pre为找到的路径中指向该点的边
            if(w[p]-flow[p]<=mf)///由于是从后往前 有多条瓶颈边存在时 显然要退到最前一个瓶颈边前
            {
                mf=w[p]-flow[p];
                u=v[p^1];///瓶颈边优化
            }
            ans+=mf;
            for(p=pre[aim];p;p=pre[v[p^1]])
            {
                flow[p]+=mf;
                flow[p^1]-=mf;
            }
        }
        for(p=cur[u];p;p=nexte[p])
        if(dist[u]==dist[v[p]]+1&&w[p]>flow[p])
        break;
        if(p)
        {
            cur[u]=p;
            pre[v[p]]=p;
            u=v[p];
        }
        else
        {
            if(0==--num[dist[u]])break;///gap优化
            cur[u]=firste[u];///重置当前弧
            int mindist=node;
            for(p=firste[u];p;p=nexte[p])
            if(w[p]>flow[p])
            mindist=imin(mindist,dist[v[p]]);
            dist[u]=mindist+1;
            ++num[dist[u]];
            if(u!=start)u=v[pre[u]^1];
        }
    }
}

  评论这张
 
阅读(114)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017