不能再水的题了。
Dinic算法,比EK更快。
想要学习请看链接 https://comzyh.com/blog/archives/568/
并附上我的模板(其实和comzyh大神的一样)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int tab[][],dis[],d[],n,m;
bool bfs()
{
int i,head=,tail=;
memset(d,,sizeof(d));
memset(dis,0xff,sizeof(dis));
d[]=; dis[]=;
while (head<=tail)
{
for (i=;i<=n;++i)
if ((dis[i]<)&&(tab[d[head]][i]>))
{
dis[i]=dis[d[head]]+;
tail++; d[tail]=i;
}
head++;
}
if (dis[n]>) return ;
else return ;
}
int wll(int x,int low)
{
int i,a=; if (x==n) return low;
for (i=;i<=n;++i)
if ((tab[x][i]>)&&(dis[i]==dis[x]+)&&(a=wll(i,min(low,tab[x][i]))))
{
tab[x][i]-=a;
tab[i][x]+=a;
return a;
}
return ;
}
int main()
{
scanf("%d %d\n",&m,&n);
int i,j,u,v,flow,ans=,at;
memset(tab,,sizeof(tab));
for (i=;i<=m;++i)
{
scanf("%d %d %d\n",&u,&v,&flow);
tab[u][v]+=flow;
}
while (bfs())
{
while (at=wll(,0x7fffffff)) ans+=at;
}
printf("%d\n",ans);
}
模板题 codevs 1993 草地排水 想学习的请看链接的更多相关文章
-
Codevs 1993 草地排水
1993 草地排水 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 在农夫约翰的农场上,每逢下雨,Bessie最喜欢的三叶草地 ...
-
codevs 1993草地排水
1993 草地排水
-
codevs 1993 草地排水 USACO
/*Dinic*/ #include<iostream> #include<cstdio> #include<cstring> #include<queue& ...
-
想学习SEO可以看哪些书籍
http://www.wocaoseo.com/thread-28-1-1.html 除了一些常见的比如入门推荐<走进搜索引擎>和进阶推荐<这就是搜索引擎--核心技术详解>之外 ...
-
CODEVS——T 1993 草地排水 USACO
http://codevs.cn/problem/1993/ 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题解 查看运行结果 题目描述 De ...
-
【CodeVS】1993草地排水
题目描述 Description 在农夫约翰的农场上,每逢下雨,Bessie最喜欢的三叶草地就积聚了一潭水.这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间.因此,农夫约翰修建了一套排水 ...
-
【最大流】【CODEVS】1993 草地排水
[算法]网络流-最大流(dinic) [题解]http://www.cnblogs.com/onioncyc/p/6496532.html #include<cstdio> #includ ...
-
AC日记——草地排水 codevs 1993
1993 草地排水 USACO 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题解 题目描述 Description 在农夫约翰的农场上,每 ...
-
- >; 网络流(【最大流】草地排水模板题)
1993 草地排水 USACO 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题解 题目描述 Description 在农夫约翰的农场上,每 ...
随机推荐
-
简单实用的HTML代码
简单实用的HTML代码 一.HTML各种命令的代码: 1.文本标签(命令) <pre></pre> 创建预格式化文本 <h1></h1> 创建最大的标题 ...
-
zju2676 Network Wars 分数规划+网络流
题意:给定无向图,每条边有权值,求该图的一个割集,是的该割集的平均边权最小 Amber的<最小割模型在信息学竞赛中的应用>中讲的很清楚了. 二分答案k,对每条边进行重新赋值为原边权-k,求 ...
-
【Unity编程】Unity中关于四元数的API详解
本文为博主原创文章,欢迎转载,请保留出处:http://blog.csdn.net/andrewfan Unity中关于四元数的API详解 Quaternion类 Quaternion(四元数)用于计 ...
-
Ubuntu出现ERR_PROXY_CONNECTION_FAILED错误解决方案
我是Ubuntu新手,因为想查看国外的资料,然后安装了灯笼,结果打开谷歌浏览器出现了ERR_PROXY_CONNECTION_FAILED错误,未连接到互联网,代理服务器出现错误,然后Firefox也 ...
-
Android毕业设计-微圈
勤拂拭软件出品,必属精品 : 勤拂拭软件 去年做了一个类似于我的朋友圈的项目,主要功能就是用户可以实时发表自己的动态,好友可以评论点赞什么的,可以建群,聊天啊,拉黑啊,反正是一个不错的社交软件,包含服 ...
-
EntityFramework Core指定更新导航属性了解一下?
前言 本文来自和何镇汐大哥的探讨,很多时候我习惯于和别人交流过后会思考一些问题,无论是天马行空还是浅薄的想法都会记录下来,或许看到此博文的您能给我更多的思考,与人交流总能收获很多东西,出发点不一样则结 ...
-
springcloud学习第一坑
我是根据周立先生所写的<Spring+Cloud与Docker微服务架构实战>来学习SpringCloud的,我会记录下来我日常遇到的所有问题,包括但不仅只包括SpringCloud的问题 ...
-
input accept属性限制文件上传格式
上传文件的类型:具体做法如下所示: 注意:accept属性可以限制上传格式,其有兼容性如下 <1>上传.csv格式的 <input text="file" acc ...
-
Win10系统安装Office2016错误,提示需要更新客户端的解决方法
下载Troubleshoot.zip 运行 OffScrubC2R.vbs ok
-
php -- 可变变量
有时候使用可变变量名是很方便的.就是说,一个变量的变量名可以动态的设置和使用.一个普通的变量通过声明来设置,例如: <?php $a = 'hello'; ?> 一个可变变量获取了一个普通 ...