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

推荐阅读

const
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
const
单击后为什么远程通知操作无效？ - Why remote notification action is doing nothing after clicking?

IhaveconfiguredanactionforaremotenotificationwhenitarrivestomyiOsapp.Iwanttwodiff ... [详细]

蜡笔小新 2023-12-14 15:57:44
const
云原生边缘计算之KubeEdge简介及功能特点

本文介绍了云原生边缘计算中的KubeEdge系统，该系统是一个开源系统，用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建，并为网络应用程序提供基础架构支持。同时，KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外，KubeEdge还支持跨平台工作，在私有、公共和混合云中都可以运行。同时，KubeEdge还提供数据管理和数据分析管道引擎的支持。最后，本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]

蜡笔小新 2023-12-14 16:49:01
const
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
const
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
const
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
const
电话号码的字母组合解题思路和代码示例

本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法，可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]

蜡笔小新 2023-12-14 18:50:22
const
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
const
Android开发笔记：使用Picasso加载网络图片等比例缩放

在Android开发中，使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法，并提供了具体的代码实现。通过获取图片的宽高，计算目标宽度和高度，并创建新图实现等比例缩放。 ... [详细]

蜡笔小新 2023-12-14 17:34:00
const
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
const
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
format
Go GUIlxn/walk 学习3.菜单栏和工具栏的具体实现

本文介绍了使用Go语言的GUI库lxn/walk实现菜单栏和工具栏的具体方法，包括消息窗口的产生、文件放置动作响应和提示框的应用。部分代码来自上一篇博客和lxn/walk官方示例。文章提供了学习GUI开发的实际案例和代码示例。 ... [详细]

蜡笔小新 2023-12-12 20:56:55
数组
Go语言实现堆排序的详细教程

本文主要介绍了Go语言实现堆排序的详细教程，包括大根堆的定义和完全二叉树的概念。通过图解和算法描述，详细介绍了堆排序的实现过程。堆排序是一种效率很高的排序算法，时间复杂度为O(nlgn)。阅读本文大约需要15分钟。 ... [详细]

蜡笔小新 2023-12-12 16:23:00
const
浏览器中的异常检测算法及其在深度学习中的应用

本文介绍了在浏览器中进行异常检测的算法，包括统计学方法和机器学习方法，并探讨了异常检测在深度学习中的应用。异常检测在金融领域的信用卡欺诈、企业安全领域的非法入侵、IT运维中的设备维护时间点预测等方面具有广泛的应用。通过使用TensorFlow.js进行异常检测，可以实现对单变量和多变量异常的检测。统计学方法通过估计数据的分布概率来计算数据点的异常概率，而机器学习方法则通过训练数据来建立异常检测模型。 ... [详细]

蜡笔小新 2023-12-12 16:22:39
const
Java自带的观察者模式及实现方法详解

本文介绍了Java自带的观察者模式，包括Observer和Observable对象的定义和使用方法。通过添加观察者和设置内部标志位，当被观察者中的事件发生变化时，通知观察者对象并执行相应的操作。实现观察者模式非常简单，只需继承Observable类和实现Observer接口即可。详情请参考Java官方api文档。 ... [详细]

蜡笔小新 2023-12-12 13:52:38

手机用户2502873443

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

Tags | 热门标签

RankList | 热门文章