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

云水居

云在青山水在天,人在江湖不得闲

 
 
 

日志

 
 

解决网络最大流问题USACO4.2.1的Dinic算法  

2010-07-02 10:31:15|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

查看全文


解决网络最大流问题的算法很多,Dinic 是其中比较快的算法之一,虽然传说中ISAP是最快的,但是用Dinic求解USACO的4.2.1已经足够了
USACO 上提供的网编流算法思想是,找一个增广路径,然后增广流量,直到没有增广路径为止。
这是有两个问题:什么是增广路径?什么叫增广流量?
增广路径:就是从源点到终点的一条路径
增广流量:首先找到增广路径上的最小流x,然后对增广路径上的每条边,减去x,并反向增加x
如: 源点1,终点8。1->3流为20, 3->5流为10, 5->8流为30,则最小流为10,1->3变为20-10,3->5变为10-10,5->8变为30-10,3->1的流量增加10,5->3的流量增加10,8->5的流量增加10
算法流程为
maxflow = 0
while 有增广路径
  maxflow += 最小流
  沿增广路径 增广流量
增广流量很简单,就是简单地修改图的边的,因此,主要的问题就是如何找增广路径。
最简单的办法是直接DFS,在USACO上可以过6个测试点,如果改用邻接表存储图的边,则可以过7个测试点,如果在增广流量的时候把流量为0的路径从邻接表中去除,就可以过8个测试点。要想过下面的4个测试点,就要优化了。
瓶颈在DFS上,当然就要用BFS优化,但是BFS的空间复杂度太高,因此采用BFS和DFS结合的方法,先用BFS对每个点标号,然后根据标号进行DFS。
如何标号:将源点S标为0,S的邻接点标为1,S的邻接点的未标号的邻接点标为2,...用BFS实现这个很简单
如何根据标号进行DFS:只有比该接点的标号多1的邻接点,才递归DFS,否则跳过。
附上程序:
/*
ID: hankjin1
LANG: C++
TASK: ditch
*/
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

//note: TLE of test 8 if no 0 dist path removed
//note: TLE of test 9
int N,M;
int ditch[201][201];
int path[201][201];

bool used[201];
int seq[201];
int bestseq[201];
int minV;
inline void add(int from, int to, int v){
    if(ditch[from][to]==0){
        path[from][ ++path[from][0] ] = to;
    }
    ditch[from][to]+=v;
}
inline void rm(int from, int to, int v){
    ditch[from][to]-=v;
    if(ditch[from][to]==0){
        for(int i=1;i<=path[from][0];i++){
            if(path[from][i]==to){
                path[from][i]=path[from][ path[from][0] ];
                break;
            }
        }
        p

查看全文

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

历史上的今天

评论

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

页脚

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