开发笔记:最大流hihocoder1369:网络流一·FordFulkerson算法

作者：手机用户2502873443 | 来源：互联网 | 2023-10-16 16:42

http://hihocoder.com/problemset/problem/1369?sid=1328132参考 https://blog.

http://hihocoder.com/problemset/problem/1369?sid=1328132

参考 https://blog.csdn.net/a1799342217/article/details/73195243

https://blog.csdn.net/a519781181/article/details/51908303

【AC1】

#include<iostream>
#include
#include
#include<string>
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n,m;
const int maxn=5e2+2;
const int maxm=2e4+2;
const int inf=0x3f3f3f3f;
int maxflow;
struct edge{
int to;
int nxt;
int w;
}e[2*maxm];
int head[maxn];
int tot;
int fa[maxn];
int mp[maxn][maxn];
bool vis[maxn];
void init(){
memset(mp,-1,sizeof(mp));
memset(head,-1,sizeof(head));
tot=0;
maxflow=0;
}
void add(int u,int v){
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot++;
}
bool bfs(int s,int t){
memset(vis,false,sizeof(vis));
memset(fa,-1,sizeof(fa));
queue<int> Q;
Q.push(s);
while(!Q.empty()){
int u=Q.front();
Q.pop();
if(u==t) return true;
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]&&mp[u][v]){
fa[v]=u;
Q.push(v);
}
}
}
return false;
}
int max_flow(int s,int t){
int flow=0;
// int cnt=0;
while(bfs(s,t)){
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<// }
// cout<// }
// cout<<"**********************"< // cnt++;
int u=t;
int delta=inf;
while(fa[u]!=-1){
// cout<
delta=min(delta,mp[fa[u]][u]);
u=fa[u];
}
// cout< // cout<
flow+=delta;
u=t;
while(fa[u]!=-1){
mp[fa[u]][u]-=delta;
mp[u][fa[u]]+=delta;
u=fa[u];
}
}
return flow;
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
int u,v,c;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&c);
if(mp[u][v]==-1){
add(u,v);
add(v,u);
mp[u][v]=c;
mp[v][u]=0;
}else{
mp[u][v]+=c;
}
}
int ans=max_flow(1,n);
printf("%d
",ans);
}
return 0;
}

【AC2】

#include
#include
#include
#include<string>
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n,m;
const int maxn=5e2+2;
const int maxm=2e4+2;
const int inf=0x3f3f3f3f;
struct edge{
int to;
int nxt;
int w;
}e[maxm<<1];
int head[maxn];
struct node{
int x;
int e;
}fa[maxn];
bool vis[maxn];
int tot;
void init(){
memset(head,-1,sizeof(head));
tot=0;
}
void add(int u,int v,int c){
e[tot].to=v;
e[tot].w=c;
e[tot].nxt=head[u];
head[u]=tot++;
}
bool bfs(int s,int t){
memset(vis,false,sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s]=true;
while(!Q.empty()){
int u=Q.front();
Q.pop();
if(u==t) return true;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
int w=e[i].w;
if(!vis[v]&&w){
Q.push(v);
vis[v]=true;
fa[v].x=u;
fa[v].e=i;
}
}
}
return false;
}
int work(){
int s=1,t=n;
for(int i=1;i<=n;i++){
fa[i].e=-1;
fa[i].x=-1;
}
int ans=0;
while(bfs(s,t)){
int delta=inf;
int u=t;
while(fa[u].x!=-1){
delta=min(delta,e[fa[u].e].w);
u=fa[u].x;
}
ans+=delta;
u=t;
while(fa[u].x!=-1){
int i=fa[u].e;
e[i].w-=delta;
e[i^1].w+=delta;
u=fa[u].x;
}
for(int i=1;i<=n;i++){
fa[i].e=-1;
fa[i].x=-1;
}
}
return ans;
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
int u,v,c;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
add(v,u,0);
}
int ans=work();
printf("%d
",ans);
}
return 0;
}

推荐阅读

include
每日精选Codeforces训练题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）

题目涉及三种不同类型的算法问题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）。其中，1119E的问题背景是有n种不同长度的棍子，长度分别为2^0, 2^1, …, 2^(n-1)，每种棍子的数量为a[i]。任务是计算可以组成的三角形数量。根据三角形的性质，任意两边之和必须大于第三边。该问题可以通过贪心算法高效解决，通过合理选择棍子组合来最大化三角形的数量。 ... [详细]

蜡笔小新 2024-11-03 11:42:58
include
洛谷 P1344 坏牛奶追踪问题（最小割算法应用）

在洛谷 P1344 的坏牛奶追踪问题中，第一问要求计算最小割，而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值，可以在求解最小割时优先选择边数较少的方案，从而同时解决两个问题。这种策略不仅简化了问题的求解过程，还确保了结果的最优性。 ... [详细]

蜡笔小新 2024-11-07 14:50:22
include
寒假作业解析：第三周 2月12日第7题

尽快完成之前的练习任务！每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析：通过对比不同路线的等待时间，可以找到最优解。此问题可以通过动态规划或贪心算法来解决，具体取决于路线的复杂性和约束条件。 ... [详细]

蜡笔小新 2024-11-06 14:33:36
include
POJ 2777：线段树的懒惰更新策略分析与实现

题目链接：POJ 2777。问题描述：给定一个区域，需要进行多次涂色操作，并在每次操作后查询某个区间内的不同颜色数量。解决方案：由于题目中颜色种类不超过30种，可以利用线段树的懒惰更新策略来高效处理这些操作。通过懒惰标记，避免了不必要的节点更新，从而显著提高了算法的效率。此外，该方法还能有效应对大规模数据输入，确保在合理的时间内完成所有操作。 ... [详细]

蜡笔小新 2024-11-03 15:22:44
copy
探索利用JavaScript实现集合的对称差集算法

本文探讨了利用JavaScript实现集合的对称差集算法的方法。该算法旨在处理多个数组作为输入参数，同时保留每个数组中元素的原始顺序。算法不会移除单个数组内的重复元素，但会删除在不同数组之间出现的重复项。通过这种方式，能够有效地计算出多个数组的对称差集。 ... [详细]

蜡笔小新 2024-11-06 19:31:06
include
2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南

2012年9月12日，优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分，有一道题目涉及中国人的血型分布情况，具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中，至少有一人为B型血的概率不低于90%，则需要选取的最少人数是多少？该问题不仅考察了概率统计的基本知识，还要求考生具备一定的逻辑推理能力。 ... [详细]

蜡笔小新 2024-11-06 15:25:14
include
STL进阶指南：第十篇深入解析全排列算法

在编程笔试和面试中，全排列算法因其适中的难度而备受青睐，不仅能够考察应聘者的算法基础，还能测试其对递归和回溯的理解。本文将深入解析全排列算法的实现原理，探讨其应用场景，并提供优化建议，帮助读者更好地掌握这一重要算法。 ... [详细]

蜡笔小新 2024-11-06 13:36:33
include
蓝桥杯算法实战：节点选取策略优化分析

本文针对蓝桥杯算法竞赛中的节点选取策略进行了深入分析与优化。通过对比不同节点选择方法的效果，提出了基于贪心算法和动态规划的综合优化方案，旨在提高算法效率和准确性。实验结果表明，该优化策略在处理大规模数据集时表现出色，显著提升了算法性能。 ... [详细]

蜡笔小新 2024-11-06 12:51:58
include
ICM Technex 2017与Codeforces第400轮（合并组）C题：莫莉的化学物质分析

在解决区间相关问题时，我发现自己经常缺乏有效的思维方式，即使是简单的题目也常常需要很长时间才能找到解题思路，而一旦得到提示便能迅速理解。题目要求对一个包含n个元素的数组进行操作，并给出一个参数k，具体任务是…… ... [详细]

蜡笔小新 2024-11-05 15:59:59
include
2021-2022 ACM集训队月度编程挑战赛第二轮：最大值与最小值的选择

在2021-2022 ACM集训队月度编程挑战赛第二轮中，题目“最大值与最小值的选择”要求参赛者处理一个包含n个元素的数组，并给定一个整数k。任务是通过选择特定的子数组，计算并返回这些子数组的最大值和最小值之间的差值。该问题考验了选手对数组操作和优化算法的理解与应用能力。 ... [详细]

蜡笔小新 2024-11-03 00:35:21
include
POJ 3083：糖果 children 的 DFS 和 BFS 算法探索

题目链接：http://poj.org/problem?id=3083。题目描述：给定一个迷宫，其中 'S' 表示起点，'E' 表示终点，'#' 表示墙壁，'.' 表示可通行的道路。起点和终点均位于迷宫的边界上，并且保证存在唯一路径。任务是求从起点 'S' 到终点 'E' 的最短路径步数，且优先考虑向左转弯。通过深度优先搜索（DFS）和广度优先搜索（BFS）算法进行路径探索，分析两种方法的优劣及适用场景。 ... [详细]

蜡笔小新 2024-11-02 16:18:27
include
数据结构详解：链栈中的元素入栈与出栈操作分析

链栈虽然通常以数组作为底层实现，但也可以采用链表来构建Stack类。在这种情况下，空堆栈通过NULL指针表示。当新元素被压入堆栈时，它会被添加到链表的头部，从而实现高效的入栈操作。此外，出栈操作则通过移除链表头部的节点来完成，确保了操作的时间复杂度为O(1)。这种设计不仅简化了内存管理，还提高了动态数据处理的灵活性。 ... [详细]

蜡笔小新 2024-11-07 17:45:16
request
Squaretest：自动生成功能测试代码的高效插件

本文将介绍一款名为Squaretest的高效插件，该工具能够自动生成功能测试代码。使用这款插件的主要原因是公司近期加强了代码质量的管控，对各项目进行了严格的单元测试评估。Squaretest不仅提高了测试代码的生成效率，还显著提升了代码的质量和可靠性。 ... [详细]

蜡笔小新 2024-11-07 15:34:27
request
手指触控|Android电容屏幕驱动调试指南

手指触控|Android电容屏幕驱动调试指南 ... [详细]

蜡笔小新 2024-11-07 01:42:20
include
开发心得：成为SGU475智能筏工的策略与技巧

开发心得：成为SGU475智能筏工的策略与技巧 ... [详细]

蜡笔小新 2024-11-04 17:38:03

手机用户2502873443

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章