最大流入门题目 - poj 1273
2024-09-05 03:28:24
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.
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 题意 : 给你一个源点和一个汇点,再给你一些中间边,同时给你他们边上的容量,求从源点到汇点最大流量是多少?
思路分析 :网络流板子题
代码示例 :
using namespace std;
#define ll long long
const int maxn = 205;
const int mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f; int n, m;
struct node
{
int next, v, flow; // flow可以理解为容量限制
}e[maxn<<1];
int cnt;
int head[maxn];
int aim; // 目标点
int deep[maxn]; // 分层图的深度 void addedge(int u, int v, int cap){
e[cnt].v = v;
e[cnt].flow = cap;
e[cnt].next = head[u];
head[u] = cnt++;
} int que[10000]; bool bfs(int s, int t){
memset(deep, 0, sizeof(deep));
deep[s] = 1; que[0] = s; int head1 = 0, tail1 = 1;
while(head1 < tail1){
int u = que[head1++];
for(int i = head[u]; i != -1; i = e[i].next){
int v = e[i].v;
if (!deep[v] && e[i].flow){ // 判断当前的边如果还可以流
deep[v] = deep[u]+1;
que[tail1++] = v;
}
}
}
return deep[t];
} int dfs(int u, int f1){
if (u == aim || f1 == 0) return f1; // 这个优化非常的棒 int f = 0;
for(int i = head[u]; i != -1; i = e[i].next){ // 多路增广,利用dfs的特性
int v = e[i].v;
if (e[i].flow && deep[v] == deep[u]+1){
int x = dfs(e[i].v, min(f1, e[i].flow));
e[i].flow -= x; e[i^1].flow += x;
f1 -= x; f += x;
if (f1 == 0) return f; // !!!
}
}
if (!f) deep[u] = -2; // 炸点优化,若当前点的流量为 0,则在此次中没有必要再去访问该点了
return f;
} int maxflow(int s, int t){
aim = t; int ret = 0;
cnt = 0;
while(bfs(s, t)){
ret += dfs(s, inf);
}
return ret;
} int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int u, v, w; while(~scanf("%d%d", &n, &m)){
cnt = 0;
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i++){
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, 0); // 反向边的建立,并赋值 0
}
printf("%d\n", maxflow(1, m));
}
return 0;
}
最新文章
- 高级渲染技巧和代码示例 GPU Pro 7
- [LeetCode] String to Integer (atoi) 字符串转为整数
- ES5新语法forEach和map及封装原理
- 转: 带你玩转Visual Studio——带你理解多字节编码与Unicode码
- iOS:Autolayout自动布局实例
- ASP.NET 相同页面前后端之间传值
- 九度OJ 1386 旋转数组的最小数字 【算法】
- [转] iOS TableViewCell 动态调整高度
- U盘安装,FTP安装CENTOS--错误信息:Unable to read package metadata.This may be due to a missing repodata directory.
- wxpython 树形控件全选和取消全选
- Salesforce的Auto Number
- java集合类中的迭代器模式
- python之路(9)反射、包装类、动态模块导入
- Docker系列07—Dockerfile 详解
- centOS6.0虚拟机ip配置
- opencv+python 自动绿帽机
- 面试3——java集合类总结(Map)
- [Sqoop]将Hive数据表导出到Mysql
- MyBatis 遍历数组放入in中
- json转实体,json转List实体,json转泛型实体