【算法】网络流-最大流(dinic)
【题解】http://www.cnblogs.com/onioncyc/p/6496532.html
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=,inf=0x3f3f3f3f;
struct edge{int from,v,flow;}e[maxn*];
int n,m,tot=,S,T,d[maxn],q[],first[maxn],cur[maxn];
void insert(int u,int v,int flow)
{tot++;e[tot].v=v;e[tot].flow=flow;e[tot].from=first[u];first[u]=tot;}
bool bfs()
{
memset(d,-,sizeof(d));
int head=,tail=;q[head]=S;
d[S]=;
while(head!=tail)
{
int x=q[head++];if(head>=)head=;
for(int i=first[x];i;i=e[i].from)
if(d[e[i].v]==-&&e[i].flow>)
{
q[tail++]=e[i].v;d[e[i].v]=d[x]+;
if(tail>=)tail=;
}
}
if(d[T]==-)return ;else return ;
}
int dfs(int x,int a)
{
if(x==T||a==)return a;
int flow=,f;
for(int& i=cur[x];i;i=e[i].from)//当前弧优化
if(d[e[i].v]==d[x]+&&(f=dfs(e[i].v,min(a,e[i].flow)))>)
{
e[i].flow-=f;
e[i^].flow+=f;
flow+=f;
a-=f;
if(a==)break;
}
return flow;
}
int main()
{
scanf("%d%d",&m,&n);
S=;T=n;
for(int i=;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
insert(v,u,);
}
int ans=;
while(bfs())
{
for(int i=;i<=n;i++)cur[i]=first[i];
ans+=dfs(S,inf);
}
printf("%d",ans);
return ;
}
【最大流】【CODEVS】1993 草地排水的更多相关文章
-
Codevs 1993 草地排水
1993 草地排水 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 在农夫约翰的农场上,每逢下雨,Bessie最喜欢的三叶草地 ...
-
codevs 1993草地排水
1993 草地排水
-
模板题 codevs 1993 草地排水 想学习的请看链接
不能再水的题了. Dinic算法,比EK更快. 想要学习请看链接 https://comzyh.com/blog/archives/568/ 并附上我的模板(其实和comzyh大神的一样) #in ...
-
codevs 1993 草地排水 USACO
/*Dinic*/ #include<iostream> #include<cstdio> #include<cstring> #include<queue& ...
-
CODEVS——T 1993 草地排水 USACO
http://codevs.cn/problem/1993/ 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题解 查看运行结果 题目描述 De ...
-
【CodeVS】1993草地排水
题目描述 Description 在农夫约翰的农场上,每逢下雨,Bessie最喜欢的三叶草地就积聚了一潭水.这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间.因此,农夫约翰修建了一套排水 ...
-
最大流 [USACO4.2]草地排水Drainage Ditches
Background 在农夫约翰的农场上,每逢下雨,贝茜最喜欢的三叶草地就积聚了一潭水.这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间.因此,农夫约翰修建了一套排水系统来使贝茜的草地免 ...
-
AC日记——草地排水 codevs 1993
1993 草地排水 USACO 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题解 题目描述 Description 在农夫约翰的农场上,每 ...
-
- >; 网络流(【最大流】草地排水模板题)
1993 草地排水 USACO 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题解 题目描述 Description 在农夫约翰的农场上,每 ...
随机推荐
-
多看Kindle的“导出失败,请检查网络或账号”错误的解决
一直都用得好好的,今天突然不行了,报错“导出失败,请检查网络或账号”. 网上搜索,试了一下这个方法: 我目前的解决办法是:先同步至小米账户(需要联网,并在Kindle系统设置 -> 阅读 -&g ...
-
【转】Android 全屏方案(隐藏NavigationBar)
http://www.07net01.com/2015/04/822292.html 在android4.0及其以上的版本中,出现了一个很屌的东西,叫做Navigation Bar,它和Status ...
-
CASUAL_NCT
using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Da ...
-
:first :first-child .first()和.get() .eq()
:first .first()只匹配一个元素,而 :first-child 将为每个父元素匹配一个子元素 .get()得到的是dom 元素 $('li').get()没有参数返回一个数组 .eq() ...
-
ABP 源码分析汇总之 IOC
IOC的优点: 1. 依赖接口,而非实现,如下代码, 这样的好处就是,客户端根本不知道PersonService的存在,如果我们换一下IPersonService的实现,客户端不用任何修改, 说的简单 ...
-
[Winter Vacation] 语文实词虚词练习册答案
下载通道: [120个文言文实词小故事] [18个文言文虚词小故事] 120个文言文实词小故事 爱 楚人爱(宠爱)其子,虽爱(吝惜)钱财,于其子之求而无不应.其子成人,有陶氏之风独爱(喜爱)菊,众 ...
-
hdu 5895 Mathematician QSC 指数循环节+矩阵快速幂
Mathematician QSC Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Othe ...
-
应用seajs 做了个向上滚动的demo
目录结构式这样滴 sea sea-module jquery-1.10.2.min.js sea.js static css t.min.css img test test.min.js main.j ...
-
Rethinking the Inception Architecture for Computer Vision
https://arxiv.org/abs/1512.00567 Convolutional networks are at the core of most state-of-the-art com ...
-
AJAX核心--XMLHttpRequest五步法
引言: AJAX=异步Javascript + XML,AJAX是一种用于创建高速动态网页的技术. 开门见山: 解读:AJAX使用XHTML和CSS为网页表示.DOM动态显示和交互,XML进行数据交换 ...