CODEVS——T 1993 草地排水 USACO
2024-08-31 17:27:46
题目描述 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
数据范围及提示 Data Size & Hint
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; #define LL long long
const LL INF(0x7fffffff);
const int N();
int n,m,u,v,w; int head[N],sumedge;
struct Edge
{
int to,next;
LL val;
Edge(int to=,int next=,LL val=):
to(to),next(next),val(val){}
}edge[N<<];
inline void ins(int u,int v,int w)
{
edge[++sumedge]=Edge(v,head[u],w);
head[u]=sumedge;
}
struct Type_AC
{
int s,t;
LL ret;
int deep[N];
bool BFS()
{
memset(deep,-,sizeof(deep));
int tail=,hd=,que[N];
deep[s]=; que[tail++]=s;
for(;hd<tail;)
{
int fro=que[hd++];
for(int i=head[fro];i;i=edge[i].next)
{
int v=edge[i].to;
if(deep[v]==-&&edge[i].val)
{
deep[v]=deep[fro]+;
que[tail++]=v;
}
}
}
if(deep[t]!=-) return true;
return false;
}
LL DFS(int now,LL flow)
{
if(now==t||!flow) return flow;
LL go,flux=;
for(int i=head[now];i;i=edge[i].next)
{
int v=edge[i].to;
if(deep[v]!=deep[now]+||edge[i].val<=) continue;
go=DFS(v,min(edge[i].val,flow-flux));
edge[i].val-=go;
edge[i^].val+=go;
flux+=go;
if(flux==flow) return flow;
}
if(!flux) deep[now]=-;
return flux;
}
void Dinic()
{
for(;BFS();) ret+=(LL)DFS(s,INF);
}
}I_want_AC; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&u,&v,&w);
ins(u,v,(LL)w); ins(v,u,(LL));
}
I_want_AC.s=;
I_want_AC.t=m;
I_want_AC.Dinic();
printf("%lld\n",I_want_AC.ret);
return ;
}
最新文章
- 网站定位之---根据IP获得区域
- 【深入Java虚拟机】之四:类加载机制
- 【学习笔记】Struts2 应用开发步骤
- 腾讯WEB前端开发面试经历,一面二面HR面,面面不到!
- Java 关键字static final使用总结
- 原:[eclipse启动错误] JVM terminated.Exit code=2
- CVE-2014-6321 &;&; MS14-066 Microsoft Schannel Remote Code Execution Vulnerability Analysis
- dg_MeetingRoom 居中显示
- python 常用函数、内置函数清单
- Optional优雅的使用null
- Codeforces Beta Round #9 (Div. 2 Only)D
- 杂乱无章之Oracle(一)
- OpenJudge/Poj 1251 丛林中的路/Jungle Roads
- 暴力求解——POJ 3134Power Calculus
- python logging模块使用
- javaScript 设计模式系列之一:观察者模式
- 中小企业为什么要上HR系统
- tp5 $_ENV获取不到数据
- 牛刀小试——记一次帮朋友小幅优化SQL
- 编译原理---antlr实践+编译过程理解+课程理解知识点