poj-1273 Drainage Ditches(最大流基础题)
2024-08-29 16:55:52
题目链接:
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 67475 | Accepted: 26075 |
Description
Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Input
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.
Output
For each case, output a single integer, the maximum rate at which water may emptied from the pond.
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50 题意: 就是求一个1到n的最大流,入门题; 思路: 简直就是模板,有个wa点就是有重边; AC代码:
//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
const LL mod=1e9+;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int N=2e4+;
int n,m,flow[],path[],cap[][];
queue<int>qu;
int bfs()
{
while(!qu.empty())qu.pop();
mst(path,-);
path[]=;
flow[]=inf;
qu.push();
while(!qu.empty())
{
int fr=qu.front();
qu.pop();
Riep(m)
{
if(i!=&&cap[fr][i]&&path[i]==-)
{
path[i]=fr;
flow[i]=min(cap[fr][i],flow[fr]);
qu.push(i);
}
}
}
if(path[m]==-)return -;
return flow[m];
}
int maxflow()
{
int sum=;
int temp,now,pre;
while()
{
temp=bfs();
if(temp==-)break;
sum+=temp;
now=m;
while(now!=)
{
pre=path[now];
cap[pre][now]-=temp;
cap[now][pre]+=temp;
now=pre;
}
}
return sum;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int u,v,w;
mst(cap,);
Riep(n)
{
scanf("%d%d%d",&u,&v,&w);
cap[u][v]+=w;
}
printf("%d\n",maxflow());
} return ;
}
最新文章
- Javaweb命名规则
- Java数据结构——容器总结
- as关键词还有另外一个用途,那就是修改 方法 的访问控制
- C++中 destory() 和deallocate()以及delete函数的相关性和区别性
- runc start container流程分析
- 3.求m+mm+mmm+…+m…m(n个)的和,其中m为1~9之间的整数。 例如,当m=3、n=4时,求3+33+333+3333的和。
- Eclipse 下如何引用另一个项目的资源文件
- hdu1753java(大数相加)---BigDecimal类
- 系统共享内存的修改(ORA-27102: out of memory)
- 1.4.2. 实现 Core Data Helper 类(Core Data 应用程序实践指南)
- 输入三个整数x、y、z,请把这三个数由小到大输出
- MySQL中的完整性约束
- Hyperledger Fabric 1.0 从零开始(五)——运行测试e2e
- 对象转字典 iOS
- WPF布局的应用
- 国内最全的Spring Boot系列之二
- oracel 日期查询
- sql数据库之多库查询
- iOS 开发的一些网址
- kvm图形化管理工具
热门文章
- Strom运行监控
- java list实现树形结构
- PHP实现INT型,SHORT型,STRING转换成BYTE数组
- 【postMan】发送post请求,返回错误码415
- 【Windows7】win7启动 报错 AutoIt错误,不能打开脚本文件
- 【转】Code Your Own PHP MVC Framework in 1 Hour
- shell mysql 直接创建表
- Spark MLlib Deep Learning Convolution Neural Network (深度学习-卷积神经网络)3.2
- ubuntu如何修改root密码
- 淘宝数据库OceanBase SQL编译器部分 源码阅读--生成物理查询计划