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

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

【算法】网络流-最大流(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 草地排水的更多相关文章

  1. Codevs 1993 草地排水

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

  2. codevs 1993草地排水

    1993 草地排水

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

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

  4. codevs 1993 草地排水 USACO

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

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

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

  6. 【CodeVS】1993草地排水

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

  7. 最大流 &lbrack;USACO4&period;2&rsqb;草地排水Drainage Ditches

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

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

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

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

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

随机推荐

  1. 多看Kindle的&OpenCurlyDoubleQuote;导出失败&comma;请检查网络或账号”错误的解决

    一直都用得好好的,今天突然不行了,报错“导出失败,请检查网络或账号”. 网上搜索,试了一下这个方法: 我目前的解决办法是:先同步至小米账户(需要联网,并在Kindle系统设置 -> 阅读 -&g ...

  2. 【转】Android 全屏方案(隐藏NavigationBar)

    http://www.07net01.com/2015/04/822292.html 在android4.0及其以上的版本中,出现了一个很屌的东西,叫做Navigation Bar,它和Status ...

  3. CASUAL&lowbar;NCT

    using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Da ...

  4. :first :first-child &period;first&lpar;&rpar;和&period;get&lpar;&rpar; &period;eq&lpar;&rpar;

    :first .first()只匹配一个元素,而 :first-child 将为每个父元素匹配一个子元素 .get()得到的是dom 元素  $('li').get()没有参数返回一个数组 .eq() ...

  5. ABP 源码分析汇总之 IOC

    IOC的优点: 1. 依赖接口,而非实现,如下代码, 这样的好处就是,客户端根本不知道PersonService的存在,如果我们换一下IPersonService的实现,客户端不用任何修改, 说的简单 ...

  6. &lbrack;Winter Vacation&rsqb; 语文实词虚词练习册答案

    下载通道: [120个文言文实词小故事] [18个文言文虚词小故事] 120个文言文实词小故事 爱   楚人爱(宠爱)其子,虽爱(吝惜)钱财,于其子之求而无不应.其子成人,有陶氏之风独爱(喜爱)菊,众 ...

  7. hdu 5895 Mathematician QSC 指数循环节&plus;矩阵快速幂

    Mathematician QSC Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Othe ...

  8. 应用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 ...

  9. 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 ...

  10. AJAX核心--XMLHttpRequest五步法

    引言: AJAX=异步Javascript + XML,AJAX是一种用于创建高速动态网页的技术. 开门见山: 解读:AJAX使用XHTML和CSS为网页表示.DOM动态显示和交互,XML进行数据交换 ...