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

时间:2021-04-17 00:13:42

不能再水的题了。

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 草地排水 想学习的请看链接的更多相关文章

  1. Codevs 1993 草地排水

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

  2. codevs 1993草地排水

    1993 草地排水

  3. codevs 1993 草地排水 USACO

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

  4. 想学习SEO可以看哪些书籍

    http://www.wocaoseo.com/thread-28-1-1.html 除了一些常见的比如入门推荐<走进搜索引擎>和进阶推荐<这就是搜索引擎--核心技术详解>之外 ...

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

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

  6. 【CodeVS】1993草地排水

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

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

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

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

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

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

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

随机推荐

  1. 简单实用的HTML代码

    简单实用的HTML代码 一.HTML各种命令的代码: 1.文本标签(命令) <pre></pre> 创建预格式化文本 <h1></h1> 创建最大的标题 ...

  2. zju2676 Network Wars 分数规划&plus;网络流

    题意:给定无向图,每条边有权值,求该图的一个割集,是的该割集的平均边权最小 Amber的<最小割模型在信息学竞赛中的应用>中讲的很清楚了. 二分答案k,对每条边进行重新赋值为原边权-k,求 ...

  3. 【Unity编程】Unity中关于四元数的API详解

    本文为博主原创文章,欢迎转载,请保留出处:http://blog.csdn.net/andrewfan Unity中关于四元数的API详解 Quaternion类 Quaternion(四元数)用于计 ...

  4. Ubuntu出现ERR&lowbar;PROXY&lowbar;CONNECTION&lowbar;FAILED错误解决方案

    我是Ubuntu新手,因为想查看国外的资料,然后安装了灯笼,结果打开谷歌浏览器出现了ERR_PROXY_CONNECTION_FAILED错误,未连接到互联网,代理服务器出现错误,然后Firefox也 ...

  5. Android毕业设计-微圈

    勤拂拭软件出品,必属精品 : 勤拂拭软件 去年做了一个类似于我的朋友圈的项目,主要功能就是用户可以实时发表自己的动态,好友可以评论点赞什么的,可以建群,聊天啊,拉黑啊,反正是一个不错的社交软件,包含服 ...

  6. EntityFramework Core指定更新导航属性了解一下?

    前言 本文来自和何镇汐大哥的探讨,很多时候我习惯于和别人交流过后会思考一些问题,无论是天马行空还是浅薄的想法都会记录下来,或许看到此博文的您能给我更多的思考,与人交流总能收获很多东西,出发点不一样则结 ...

  7. springcloud学习第一坑

    我是根据周立先生所写的<Spring+Cloud与Docker微服务架构实战>来学习SpringCloud的,我会记录下来我日常遇到的所有问题,包括但不仅只包括SpringCloud的问题 ...

  8. input accept属性限制文件上传格式

    上传文件的类型:具体做法如下所示: 注意:accept属性可以限制上传格式,其有兼容性如下 <1>上传.csv格式的 <input text="file" acc ...

  9. Win10系统安装Office2016错误&comma;提示需要更新客户端的解决方法

    下载Troubleshoot.zip 运行 OffScrubC2R.vbs ok

  10. php -- 可变变量

    有时候使用可变变量名是很方便的.就是说,一个变量的变量名可以动态的设置和使用.一个普通的变量通过声明来设置,例如: <?php $a = 'hello'; ?> 一个可变变量获取了一个普通 ...