pku 1273 Drainage Ditches 最大流入门基础题

﹏ヽ暗。殇╰゛Y 2022-07-26 05:20 26阅读 0赞

\#include <iostream> \#include <cstdio> \#include <cstring> \#include <queue> using namespace std; \#define MAX\_VALUE 0x7fffffff int map\[201\]\[201\]; int path\[201\]; //path\[i\]: 路径, 保存i点的前一节点path\[i\] int flow\[201\]; //flow\[i\]: 保存此节点的最大流 int N, M; int bfs() \{ memset(path, -1, sizeof(path)); queue<int> q; q.push(1); flow\[1\] = MAX\_VALUE; while(!q.empty()) \{ int v = q.front(); q.pop(); if(v == M) return flow\[v\]; for(int i = 1; i <= M; ++i) \{ if(i != v && path\[i\] == -1 && map\[v\]\[i\]) \{ path\[i\] = v; flow\[i\] = flow\[v\]>map\[v\]\[i\]?map\[v\]\[i\]:flow\[v\]; //寻找此路径上的最大流 q.push(i); \} \} \} return -1; \} int edmonds\_karp() \{ int max\_flow = 0; int v, cur, pre; while ((v = bfs()) != -1) //寻找增广路径 \{ max\_flow += v; cur = M; while (cur != 1) \{ pre = path\[cur\]; map\[pre\]\[cur\] -= v; //正向capicity减 map\[cur\]\[pre\] += v; //反向加capicity cur = pre; \} \} return max\_flow; \} int main() \{ while(scanf("%d%d", &N, &M) != EOF) \{ int s, e, v; memset(map, 0, sizeof(map)); for(int i = 0; i < N; ++i) \{ scanf("%d%d%d", &s, &e, &v); map\[s\]\[e\] += v; \} printf("%d/n", edmonds\_karp()); \} return 0; \}

发表评论取消回复

表情：

评论列表（有 0 条评论，26人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java IO流入门指南

Java IO流是Java编程中非常重要的一部分，它可以帮助开发者实现文件的读写、网络通信等功能。如果你想学习Java IO流，那么本文将为你提供一些入门指南。 1. IO

女爷i/ 2024年03月24日 10:23/ 0 赞/ 56 阅读

相关 POJ 1273-Drainage Ditches（最大流-Edmond-Karp算法/模板）

Drainage Ditches <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000M

蔚落/ 2022年09月24日 06:20/ 0 赞/ 155 阅读

相关 hdoj 1532 Drainage Ditches 题解（最大流）

Drainage Ditches Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (

梦里梦外;/ 2022年08月26日 04:52/ 0 赞/ 147 阅读

相关 pku 1273 Drainage Ditches 最大流入门基础题

\include <iostream> \include <cstdio> \include <cstring> \include <queue> using namespac

﹏ヽ暗。殇╰゛Y/ 2022年07月26日 05:20/ 0 赞/ 27 阅读

相关 java8 stream流入门

学习流之前建议先学习lambda表达式的应用。 1.流简介 Stream的优点：声明性，可复合，可并行。这三个特性使得stream操作更简洁，更灵活

落日映苍穹つ/ 2022年06月10日 03:49/ 0 赞/ 204 阅读

相关 HDU 1532 Drainage Ditches（最大流+EK算法模板题）

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover

亦凉/ 2022年06月09日 10:25/ 0 赞/ 170 阅读

相关 HDU - 1532 Drainage Ditches （网络流-最大流）

题意：题意很明显，是一个典型的最大流问题。运货起始点，序号是1，终点站序号是n 。点代表城市，边代表该段管道所能够承受的最大油流量。求从1->n 的最大运油的总量（一次

痛定思痛。/ 2022年06月09日 04:39/ 0 赞/ 213 阅读

相关 TOJ 4085 Drainage Ditches 最大流

描述 Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clo

一时失言乱红尘/ 2022年05月27日 04:48/ 0 赞/ 149 阅读

相关 flowable工作流入门（一）

flowable工作流入门 [Flowable下载][Flowable] 使用spring boot flowble生成所需表 <dependency>

ゝ一纸荒年。/ 2022年05月16日 14:28/ 0 赞/ 311 阅读

相关 poj 1273.PIG （最大流）

网络流关键是建图，思路在代码里 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] /

深藏阁楼爱情的钟/ 2022年01月05日 11:51/ 0 赞/ 215 阅读