开发笔记:最大流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;
}

推荐阅读

main
2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

本次考试于2016年10月25日上午7:50至11:15举行，主要涉及数学专题，特别是斐波那契数列的性质及其在编程中的应用。本文将详细解析考试中的题目，并提供解题思路和代码实现。 ... [详细]

蜡笔小新 2024-12-25 13:08:21
main
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
main
2-SAT问题学习笔记

本文介绍了一种解决二元可满足性（2-SAT）问题的方法。通过具体实例，详细解释了如何构建模型、应用算法，并提供了编程实现的细节和优化建议。 ... [详细]

蜡笔小新 2024-12-24 21:48:43
main
毕业设计：基于机器学习与深度学习的垃圾邮件（短信）分类算法实现

本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程，并提供了具体的代码示例和实验结果。 ... [详细]

蜡笔小新 2024-12-25 17:38:50
main
C++面试高频题

作者：守望者1028链接：https:www.nowcoder.comdiscuss55353来源：牛客网面试高频题：校招过程中参考过牛客诸位大佬的面经，但是具体哪一块是参考谁的我 ... [详细]

蜡笔小新 2024-12-25 12:32:36
merge
MySQL索引详解与优化

本文深入探讨了MySQL中的索引机制，包括索引的基本概念、优势与劣势、分类及其实现原理，并详细介绍了索引的使用场景和优化技巧。通过具体示例，帮助读者更好地理解和应用索引以提升数据库性能。 ... [详细]

蜡笔小新 2024-12-25 19:52:47
main
POJ 1691 矩形涂色问题 (DFS/状态压缩DP)

本题通过将每个矩形视为一个节点，根据其相对位置构建拓扑图，并利用深度优先搜索（DFS）或状态压缩动态规划（DP）求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]

蜡笔小新 2024-12-25 18:27:21
node.js
解析猫鼬 findOne 方法返回 null 的原因

本文探讨了在通过 API 端点调用时，使用猫鼬（Mongoose）的 findOne 方法总是返回 null 的问题，并提供了详细的解决方案和建议。 ... [详细]

蜡笔小新 2024-12-25 17:40:33
main
dotnet 通过 Elmish.WPF 使用 F# 编写 WPF 应用

本文来安利大家一个有趣而且强大的库，通过F#和C#混合编程编写WPF应用，可以在WPF中使用到F#强大的数据处理能力在GitHub上完全开源Elmis ... [详细]

蜡笔小新 2024-12-25 16:06:42
main
在Linux Mint上配置Rust开发环境

本文介绍如何在Linux Mint系统上搭建Rust开发环境，包括安装IntelliJ IDEA、Rust工具链及必要的插件。通过详细步骤，帮助开发者快速上手。 ... [详细]

蜡笔小新 2024-12-25 11:22:56
header
Web前端开发中的HTML与CSS命名规范

作为一名专业的Web前端工程师，掌握HTML和CSS的命名规范是至关重要的。良好的命名习惯不仅有助于提高代码的可读性和维护性，还能促进团队协作。本文将详细介绍Web前端开发中常用的HTML和CSS命名规范，并提供实用的建议。 ... [详细]

蜡笔小新 2024-12-25 11:06:17
main
信用评分卡的Python实现与评估

本文介绍如何使用Python构建和评估信用评分卡模型，涵盖数据预处理、模型训练及验证指标选择。附带详细代码示例和视频教程链接。 ... [详细]

蜡笔小新 2024-12-25 10:16:23
main
Flutter | Key 的深度解析

在 Flutter 开发过程中，开发者经常会遇到 Widget 构造函数中的可选参数 Key。对于初学者来说，理解 Key 的作用和使用场景可能是一个挑战。本文将详细探讨 Key 的概念及其应用场景，并通过实例帮助你更好地掌握这一重要工具。 ... [详细]

蜡笔小新 2024-12-25 08:05:15
get
UC浏览器分享图片显示问题及解决方案

本文探讨了在UC浏览器中调用分享面板后，图片无法正常显示的问题，并提供了详细的解决方法和代码示例。 ... [详细]

蜡笔小新 2024-12-24 17:24:36
hash
深入剖析 DEX 赛道：从 60 大头部项目看五大趋势

本文通过分析 60 大头部去中心化交易平台（DEX），揭示了当前 DEX 赛道的五大发展趋势，包括市场集中度、跨链协议、AMM+NFT 结合、新公链崛起以及稳定币和衍生品交易的增长潜力。 ... [详细]

蜡笔小新 2024-12-24 14:51:19

手机用户2502873443

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

Tags | 热门标签

RankList | 热门文章