开发笔记:最大流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
线段树详解与实现

本文详细介绍了线段树的基本概念及其在编程竞赛中的应用，并提供了一个具体的线段树实现代码示例。 ... [详细]

蜡笔小新 2024-11-19 21:26:45
import
Singleton单例模式和DoubleChecked Locking双重检查锁定模式

问题描述现在，不管开发一个多大的系统（至少我现在的部门是这样的），都会带一个日志功能；在实际开发过程中 ... [详细]

蜡笔小新 2024-11-21 15:14:45
shell
入门指南：使用FastRPC技术连接Qualcomm Hexagon DSP

本文旨在为初学者提供关于如何使用FastRPC技术连接Qualcomm Hexagon DSP的基础知识。FastRPC技术允许开发者在本地客户端实现远程调用，从而简化Hexagon DSP的开发和调试过程。 ... [详细]

蜡笔小新 2024-11-21 10:03:34
import
java写简易五子棋游戏。

importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]

蜡笔小新 2024-11-20 17:34:54
case
linux网络子系统分析（二）—— 协议栈分层框架的建立

目录一、综述二、INET的初始化2.1INET接口注册2.2抽象实体的建立2.3代码细节分析2.3.1socket参数三、其他协议3.1PF_PACKET3.2P ... [详细]

蜡笔小新 2024-11-20 15:21:14
header
Qt中信号与槽机制对比传统回调函数的优势

在Qt框架中，信号与槽机制是一种独特的组件间通信方式。本文探讨了这一机制相较于传统的C风格回调函数所具有的优势，并分析了其潜在的不足之处。 ... [详细]

蜡笔小新 2024-11-20 10:48:37
case
编译原理中的语法分析方法探讨

本文探讨了在编译原理课程中遇到的复杂文法问题，特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略，包括递归下降解析、运算符优先级解析等，并提供了相关示例。 ... [详细]

蜡笔小新 2024-11-19 14:44:19
substring
理解浏览器历史记录（2）hashchange、pushState

阅读目录1.hashchange2.pushState本文也是一篇基础文章。继上文之后，本打算去研究pushState，偶然在一些信息中发现了锚点变 ... [详细]

蜡笔小新 2024-11-20 20:05:37
import
Android与JUnit集成测试实践

本文探讨了如何在Android项目中集成JUnit进行单元测试，并详细介绍了修改AndroidManifest.xml文件以支持测试的方法。 ... [详细]

蜡笔小新 2024-11-20 18:30:14
import
深入解析WebP图片格式及其应用

随着互联网技术的发展，无论是PC端还是移动端，图片数据流量占据了很大比重。尤其在高分辨率屏幕普及的背景下，如何在保证图片质量的同时减少文件大小，成为了亟待解决的问题。本文将详细介绍Google推出的WebP图片格式，探讨其在实际项目中的应用及优化策略。 ... [详细]

蜡笔小新 2024-11-20 16:31:47
import
利用JavaScript for循环构建九九乘法表

本文介绍如何使用JavaScript中的for循环来创建一个九九乘法表，适合初学者学习循环结构的应用。 ... [详细]

蜡笔小新 2024-11-20 16:16:22
main
c语言二元插值,二维线性插值c语言

c语言二元插值,二维线性插值c语言 ... [详细]

蜡笔小新 2024-11-20 12:20:16
main
HTML前端开发：UINavigationController与页面间数据传递详解

本文详细介绍了如何在HTML前端开发中利用UINavigationController进行页面管理和数据传递，适合初学者和有一定基础的开发者学习。 ... [详细]

蜡笔小新 2024-11-20 09:46:39
case
深入解析BCTF竞赛中的窃密木马挑战

本文详细探讨了BCTF竞赛中窃密木马题目的解题策略，重点分析了该题目在漏洞挖掘与利用方面的技巧。 ... [详细]

蜡笔小新 2024-11-19 22:36:27
dll
一种基于X_CORBA的远程对象调用实现方法

本文介绍了如何利用X_CORBA实现远程对象调用，并通过多个示例程序展示了其功能与应用，包括基础的Hello World示例、文件传输工具以及一个完整的聊天系统。 ... [详细]

蜡笔小新 2024-11-19 19:18:07

手机用户2502873443

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

Tags | 热门标签

RankList | 热门文章