Codevs 1993 草地排水

时间:2021-09-22 00:13:56

1993 草地排水

时间限制: 2 s    空间限制: 256000 KB    题目等级 : 钻石 Diamond

题目描述 Description

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

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

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

输入描述 Input Description

第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)是这条排水沟的最大容量。

输出描述 Output Description

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

样例输入 Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
样例输出 Sample Output

50

 #include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
#define INF 0x7f
int n,m,map[][]={},lays[];
bool vis[];
bool BFS(){
queue<int>q;
memset(lays,-,sizeof(lays));
lays[]=;q.push();
while(!q.empty()){
int u=q.front();q.pop();
for(int i=;i<=m;i++){
if(map[u][i]>&&lays[i]==-){
lays[i]=lays[u]+;
if(i==m)return ;
else q.push(i);
}
}
}
return ;
}
int Dinic(){
int maxf=;vector<int>st;
while(BFS()){
st.push_back();
memset(vis,,sizeof(vis));vis[]=;
while(!st.empty()){
int p=st.back();
if(p==m){
int minn,minx=INF;
for(int i=;i<st.size();i++){
int u=st[i-],v=st[i];
if(map[u][v]>&&map[u][v]<minx){
minn=u;minx=map[u][v];
}
}
maxf+=minx;
for(int i=;i<st.size();i++){
int u=st[i-],v=st[i];
map[u][v]-=minx;
map[v][u]+=minx;
}
while(!st.empty()&&st.back()!=minn){
vis[st.back()]=;st.pop_back();
}
}
else {
int i;
for(i=;i<=m;i++){
if(map[p][i]>&&lays[i]==
lays[p]+&&!vis[i]){
vis[i]=;st.push_back(i);
break;
}
}
if(i>m)st.pop_back();
}
}
}
return maxf;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,a,b,c;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
map[a][b]+=c;
}
printf("%d\n",Dinic());
return ;
}

Codevs 1993 草地排水的更多相关文章

  1. codevs 1993草地排水

    1993 草地排水

  2. 模板题 codevs 1993 草地排水 想学习的请看链接

    不能再水的题了. Dinic算法,比EK更快. 想要学习请看链接   https://comzyh.com/blog/archives/568/ 并附上我的模板(其实和comzyh大神的一样) #in ...

  3. codevs 1993 草地排水 USACO

    /*Dinic*/ #include<iostream> #include<cstdio> #include<cstring> #include<queue& ...

  4. CODEVS——T 1993 草地排水 USACO

    http://codevs.cn/problem/1993/  时间限制: 2 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果     题目描述 De ...

  5. 【CodeVS】1993草地排水

    题目描述 Description 在农夫约翰的农场上,每逢下雨,Bessie最喜欢的三叶草地就积聚了一潭水.这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间.因此,农夫约翰修建了一套排水 ...

  6. 【最大流】【CODEVS】1993 草地排水

    [算法]网络流-最大流(dinic) [题解]http://www.cnblogs.com/onioncyc/p/6496532.html #include<cstdio> #includ ...

  7. AC日记——草地排水 codevs 1993

    1993 草地排水 USACO  时间限制: 2 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond 题解       题目描述 Description 在农夫约翰的农场上,每 ...

  8. - &gt&semi; 网络流(【最大流】草地排水模板题)

    1993 草地排水 USACO  时间限制: 2 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond 题解       题目描述 Description 在农夫约翰的农场上,每 ...

  9. codevs1993 草地排水(最大流)

    1993 草地排水 USACO  时间限制: 2 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond   题目描述 Description 在农夫约翰的农场上,每逢下雨,Bes ...

随机推荐

  1. 4个mysql客户端工具的比较

    mysql是我以前学习和练习所使用的数据,现在在工作中也在使用,之前公司里用oracle,我在做自己的东西的时候觉得用oracle太不方便,于是就找了mysql(当时也考虑过sqlserver,觉得还 ...

  2. Manacher

    HDU 3068 Manacher裸题 #include <cstdio> #include <cstring> ; ],STR[Maxn<<]; ],Id,Mx; ...

  3. 篇2 &Tab;&Tab;安卓app自动化测试-初识python调用appium

    篇2              安卓app自动化测试-初识python调用appium --lamecho辣么丑 1.1概要 大家好!我是lamecho(辣么丑),上一篇也是<安卓app自动化测 ...

  4. DevOps之归纳总结

    唠叨话 关于德语关我屁事的知识点,仅提供精华汇总,具体知识点细节,参考教程网址,如需帮助,请留言. DevOps归纳总结 <DevOps功能与性能>浏览器(饼干Cookie.会话Sessi ...

  5. 基于queryperf 和 perftcpdns 的DNS压力测试

    最近在AWS上安装了PPTP VPN 做代理,手机, pad 也可以无缝FQ,甚是开心.最近工作不太忙,研究一下缓存加速的调优.系统已经安装的nscd文件级的缓存和dnsmasq,cpu级的dns缓存 ...

  6. &lbrack;Web&rsqb;&lbrack;DreamweaverCS6&rsqb;&lbrack;高中同学毕业分布去向网站&plus;服务器上挂载&rsqb;一、安装与破解DreamweaverCS6&plus;基本规划

    DreamweaverCS6安装与破解 一.背景介绍:同学毕业分布图项目计划简介 哎哎哎,炸么说呢,对于Web前端设计来说,纯手撕html部分代码实在是难受. 对于想做地图这类的就“必须”用这个老工具 ...

  7. spark之java程序开发

    spark之java程序开发 1.Spark中的Java开发的缘由: Spark自身是使用Scala程序开发的,Scala语言是同时具备函数式编程和指令式编程的一种混血语言,而Spark源码是基于Sc ...

  8. web前端(2)—— 前端技术介绍

    前端技术 前文了解了什么是前端,那么前端技术到底有哪些呢?最核心的就这三个: html/html5 css/css3 javascript 什么是HTML HyperText Markup Langu ...

  9. 表表达式,Substring&comma; CharIndex&comma; 多行数据变同一行的用法

    参考: https://www.cnblogs.com/cnki/p/9561427.html https://www.cnblogs.com/johnwood/p/6386613.html 1.表1 ...

  10. tomcat虚拟目录配置

    Tomcat6.0虚拟目录配置[转] 设虚拟目录 "site",通过 http://localhost:8080/site 访问物理路径 D:"site 文件夹里面的内容 ...