文档章节

网络流的初步应用[USACO4.2]草地排水

p
 palapromise
发布于 2017/08/30 13:24
字数 1962
阅读 3
收藏 0
点赞 0
评论 0

欢迎访问我的博客:https://flashydirox.github.io/

[USACO4.2]草地排水DrainageDitches

  • 网络流的应用日渐广泛,[USACO4.2]草地排水作为一道最大流的基本问题,可以说是裸的模板最大流问题,在此将其作为网络流的第一道例题,正方便了对网络流的学习以及理解,也为以后的诸多变形打下基础。

题目简介:

  • 中文翻译(转自nocow):

  • 农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局(起点为水潭而终点为小溪的一张网)。需要注意的是,有些时候从一处到另一处不只有一条排水沟。

    根据这些信息,计算从水潭排水到小溪的最大流量。对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形。

    题目背景

    在农夫约翰的农场上,每逢下雨,贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间。因此,农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼(不用担心,雨水会流向附近的一条小溪)。作为一名一流的技师,农夫约翰已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量。

    题目描述

    农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局(起点为水潭而终点为小溪的一张网)。需要注意的是,有些时候从一处到另一处不只有一条排水沟。

    根据这些信息,计算从水潭排水到小溪的最大流量。对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形。

    输入输出格式

    输入格式:

    第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫John已经挖好的排水沟的数量,M是排水沟交叉点的数量。交点1是水潭,交点M是小溪。

    第二行到第N+1行: 每行有三个整数,Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点,雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。

    输出格式:

    输出一个整数,即排水的最大流量。

    输入输出样例

    输入:
    输入:
    5 4
    1 2 40
    1 4 20
    2 4 20
    2 3 30
    3 4 10
    输出:
    50

    分析:

对于一道网络流的初级问题来说,使用Dinic算法未免有些小题大 做,现在我们使用广搜的办法求解该题,在此之前我们首先需要了解一下解决此网络流问题需要的基本定义。


定义

增广路径 :可以理解为从源点s到汇点t的一条流量不为0的路径,在这里我们不考虑负流量的情况

残余流量:即当前路径下容量减去当前流量的值


​ (以上仅为一些定义,如接受扔有困难请自行移步百度)

首先,对于一个有向图,若不需直接求出两点之间的最大流量,我们可以考虑使用邻接表储存。否则使用邻接矩阵则较为方便。想要求出最大流量,我们可以不停的使用广搜寻找出可行的增广路径,对于当前搜索的增广路径上的每一个节点,每次对它所可以抵达的每一个点进行扩展,同时记录下该节点的前一个节点,这个扩展需要被扩展的点与当前节点上联通的路径的残余流量为正。当当前节点已经抵达目标节点时,即已经找到了一条可行的增广路径,则可以更新一下最优值。注意:当更新的时候,一定要给当前的流量的反向弧加上与它相等的容量。

例如:

f[u][v] = 10

则需要加上一个反向容量

c[v][u] += 10;

那么这样做的意义何在?我们有这样的一条定理:当当前残余网络上没有可行的增广路时,则找到了最大流。那么我们给它添加一个反向容量,即为下一次对增广路的搜索做出准备,以找到最大流。

具体的看下面代码实现:

代码实现:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#define REP(i, N, M) for(register int i = N; i <= M; i++)

const int MAXN = 200 + 10;
const int inf = 0x3f3f3f3f;//定义inf最大值,以便比较求出最小值

using namespace std;

queue<int>Q;//队列以进行广搜

int Capacity[MAXN][MAXN]/*存取两点间的容量*/, 
Flow[MAXN][MAXN]/*存取两点间的流量*/, Previous[MAXN];
//记录当前节点链接的上一个节点 
bool SignQ[MAXN];//标记进行判重
int N, M, Bottlenneck, cnt;

inline void IN();//输入函数

inline bool Search_Augmenting_Path();//求取增广路是否存在

inline void Search_Augmenting_Path_Bottlenneck();
//求取当前增广路上最大的流量,即残存网络下的最大流量,也即剩余的容量最小值

inline void Calc_Flow();//对当前增广路上的流量进行统计

inline void OUT();//输出

int main()
{
    IN();

    while(Search_Augmenting_Path())
      //搜索增广路是否存在, 当增广路存在时,
      //即有一条路从源点到汇点的流量可以大于0,此时还可以增加流量;
    {
        Search_Augmenting_Path_Bottlenneck();
        Calc_Flow();
    }

    OUT();

    return 0;
}

inline void IN()
{
    cin >> N >> M;
    REP(i, 1, N)
    {
        int Node_u, Node_v, Node_Capacity;
        cin >> Node_u >> Node_v >> Node_Capacity;
        Capacity[Node_u][Node_v] += Node_Capacity;
      //读取从Node_u到Node_v路径上的容量 
      //注意,从一个点到另一个点的路径可能有多条,
     // 我们可以把它们视为同一条路径,
       //其容量为从该点到另一个店的所有容量之和

    }
}

inline bool Search_Augmenting_Path()
{
    while(!Q.empty())//清空队列
        Q.pop();
    memset(SignQ, 0, sizeof(SignQ));//清空标记

    Q.push(1);//入队,开始广搜
    SignQ[1] = true;
    while(!Q.empty())
    {
        int Node = Q.front();//取出队首
        REP(i, 1, M)
        {
            if(!SignQ[i] && Capacity[Node][i] > Flow[Node][i])
            {//枚举所有结点,当容量大于当前流量时,可以汇入流量
                Q.push(i);
                SignQ[i] = true;
              //将当前节点入队,标记设为true
                Previous[i] = Node;
              //记录当前节点的上一个结点,在后面统计当前增广路的流量时需要用到
                if(i == M)
                  //当i等于M时,即找到了汇点,为一条增广路
                    return true;
            }

        }
        Q.pop();
    }
    return false;
  //否则返回false,此时没有增广路了,需要对最终答案进行统计
}

inline void Search_Augmenting_Path_Bottlenneck()
{
    Bottlenneck = inf;
  //将当前增广路的最大可行流量设为inf,即可以从这条增广路汇入源点的流量
    int Last_Node = M;
    while(Previous[Last_Node]){
      //当当前的结点不为源点时,继续执行
        Bottlenneck = 
          min(Capacity[Previous[Last_Node]][Last_Node] - Flow[Previous[Last_Node]][Last_Node], Bottlenneck); 
                //更新当前的最大可行流量,即最小的剩余容量
        Last_Node = Previous[Last_Node];
      //将当前节点跳至上一节点,继续更新Bottlenneck
    }
}

inline void Calc_Flow()
{
    int Last_Node = M;
    while(Previous[Last_Node])//当当前节点不为源点时
    {
        Flow[Previous[Last_Node]][Last_Node] += Bottlenneck;
        Capacity[Last_Node][Previous[Last_Node]] += Bottlenneck;
        Last_Node = Previous[Last_Node];
//这里很重要!!当前增广路上的每一条路径需要加上此时的最大流量,
      //同时为了返回上一节点,
      //需要将此路径的反向路径容量加上当前最大流量,
      //这使得下一次可以返回此节点以寻找下一条路
    }
}

inline void OUT()
{
    REP(i, 2, M)
    {
        cnt += Flow[1][i];
    }
    cout << cnt;
}

本文转载自:http://blog.csdn.net/lhz_cnyali/article/details/77452938

共有 人打赏支持
p
粉丝 0
博文 1
码字总数 0
作品 0
WSFC 维护模式操作粒度控制

之前曾经在WSFC日常管理操作篇和大家介绍过WSFC的维护模式,简单来说,从WSFC 2012开始,通过维护模式可以帮我们完成暂停节点,自动排水,自动回复的半自动化维护 回顾一下WSFC的维护模式运作...

老收藏家
01/29
0
0
分布式SQL引擎--Lealone

Lealone 为 HBase 提供一个分布式SQL引擎,尝试将BigTable(HBase)和 RDBMS (H2数据库) 结合的项目。 Lealone 发音 ['li:ləʊn] 这是我新造的英文单词,灵感来自于在淘宝工作期间办公桌上那些...

匿名
2013/03/20
10.7K
1
2016年山西高考答案★599551169★

台聚焦水利的1号文件、召开最高规格的中央水利工作会议,全面 部署水利改革发展,吹响了中国特色水利现代 化的进 军号。2013是水利建设快速发展的二年,随着各项政策与措施的实 施,推动了水...

dy0492096guxingu6
2016/05/10
0
0
2016年高考嗒案《623077070》包100%过

2016台聚焦水利的1号文件、召开最高规格的中央水利工作会议,全面 部署水利改革发展,吹响了中国特色水利现代 化的进 2016军号。2013是水利建设快速发展的二年,随着各项政策与措施的实 施,...

q34r5234
2016/03/09
2
0
卖2016年高考嗒案《623077070》包100%过

2016台聚焦水利的1号文件、召开最高规格的中央水利工作会议,全面 部署水利改革发展,吹响了中国特色水利现代 化的进 2016军号。2013是水利建设快速发展的二年,随着各项政策与措施的实 施,...

q34r5234
2016/03/09
0
0
FZU ~ 2150 ~ Fire Game (双点BFS)

题意:你最多可以选择两处火源,要把整个地图上的草地都点燃,火可以往上下左右四个方向扩散,能否把所有的草地都点燃,能的话输出最少时间,不能输出-1;'#'代表草地,'.'表示空地,空地不会...

ZscDst
2017/12/25
0
0
公有云DIY:使用AWS创建视频点播服务

  【IT168 应用】谷歌电视即将推出。 这是因特网所带来的、与传统的媒体不同的娱乐体验的一部分,这是一种新的、不同于传统的电视机或个人电脑的体验。   现在电视节目和电影已经可以通过...

it168网站
2010/09/03
0
0
草地上的夜

晚上九点的时候,我看书累了,就想到学校的大草地上走走。 结果躺在草地上,就不想动了,我靠着一块大石头,居然睡着了。醒来的时候,已经将近半夜12点了。 对面的图书馆大楼已经熄灯了,四周...

阮一峰
2007/05/26
0
0
优酷通过世界杯,让所有人知道:优酷真的优,真的酷!

2018世界杯如期而至,啤酒、足球、直播、小烧烤,已然成为了今夏标配。与往届世界杯不同的是,人们不再守在电视机前等直播,而是纷纷拿起手机或iPad欣赏犹如电影大片一样的比赛,不仅能看直播...

nahom
06/20
0
0
SOCKET io 中flush的坑

最近生产上出现了个问题,在A机写入的2900个字节,到B机收到只有1432个字节,初步怀疑是网络丢包或者是A机没有完全刷入流中,基于这个思路,在A机写的时候加入out.flush(); 后来在读源码的时...

马甲12345
2016/12/29
11
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!

前言 Map 这样的 Key Value 在软件开发中是非常经典的结构,常用于在内存中存放数据。 本篇主要想讨论 ConcurrentHashMap 这样一个并发容器,在正式开始之前我觉得有必要谈谈 HashMap,没有它...

crossoverJie
7分钟前
1
0
OSChina 周一乱弹 —— 你的朋友圈有点生锈了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @Devoes :分享Trademark的单曲《Only Love (电视剧《妙手仁心 II》插曲)》: 《Only Love (电视剧《妙手仁心 II》插曲)》- Trademark 手机党少...

小小编辑
今天
204
9
【面试题】盲人坐飞机

有100位乘客乘坐飞机,其中有一位是盲人,每位乘客都按自己的座位号就坐。由于盲人看不见自己的座位号,所以他可能会坐错位置,而自己的座位被占的乘客会随便找个座位就坐。问所有乘客都坐对...

garkey
今天
1
0
谈谈神秘的ES6——(二)ES6的变量

谈谈神秘的ES6——(二)ES6的变量 我们在《零基础入门JavaScript》的时候就说过,在ES5里,变量是有弊端的,我们先来回顾一下。 首先,在ES5中,我们所有的变量都是通过关键字var来定义的。...

JandenMa
今天
1
0
arts-week1

Algorithm 594. Longest Harmonious Subsequence - LeetCode 274. H-Index - LeetCode 219. Contains Duplicate II - LeetCode 217. Contains Duplicate - LeetCode 438. Find All Anagrams ......

yysue
今天
2
0
NNS拍卖合约

前言 关于NNS的介绍,这里就不多做描述,相关的信息可以查看NNS的白皮书http://doc.neons.name/zh_CN/latest/nns_background.html。 首先nns中使用的竞价货币是sgas,关于sgas介绍可以戳htt...

红烧飞鱼
今天
1
0
Java IO类库之管道流PipeInputStream与PipeOutputStream

一、java管道流介绍 在java多线程通信中管道通信是一种重要的通信方式,在java中我们通过配套使用管道输出流PipedOutputStream和管道输入流PipedInputStream完成线程间通信。多线程管道通信的...

老韭菜
今天
0
0
AB 压力测试

Ubuntu 安装AB apapt-get install apache2-utils 使用AB 压力测试 -c 并发数 -n请求总数 ab -c 3000 -n 10000 http://localhost/test/index.php AB只能测试localhost 返回结果 This is Apac......

xiawet
今天
0
0
用Python绘制红楼梦词云图,竟然发现了这个!

Python在数据分析中越来越受欢迎,已经达到了统计学家对R的喜爱程度,Python的拥护者们当然不会落后于R,开发了一个个好玩的数据分析工具,下面我们来看看如何使用Python,来读红楼梦,绘制小...

猫咪编程
今天
1
0
Java中 发出请求获取别人的数据(阿里云 查询IP归属地)

1.效果 调用阿里云的接口 去定位IP地址 2. 代码 /** * 1. Java中远程调用方法 * http://localhost:8080/mavenssm20180519/invokingUrl.action * @Title: invokingUrl * @Description: * @ret......

Lucky_Me
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部