BZOJ3396Total flow 水流

2023-10-19 17:10
文章标签 flow bzoj3396total 水流

本文主要是介绍BZOJ3396Total flow 水流,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

3396: [Usaco2009 Jan]Total flow 水流
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 304 Solved: 134
Description
这里写图片描述
这里写图片描述
Input
第1行输入N,之后N行每行描述一条水管,前两个英文字母表示水管的两端(大小写字母是不一样的),后一个整数表示水管的流量,流量不会超过1000.
Output
一个整数,表示总流量.
Sample Input
5
A B 3
B C 3
C D 5
D Z 4
B Z 6
Sample Output
3
Source
Silver
转一下数字,直接最大流。。
注意好像有小写字母。。
附上本蒟蒻的代码:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define T 26
int n,h[490001],dis[490001],head,tail,ans,sum,cnt=1,q[490001];
struct kx
{int to,next,v;
}edge[490001];int read()
{int w=0,c=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') c=-1;ch=getchar();}while (ch>='0' && ch<='9')w=w*10+ch-'0',ch=getchar();return w*c;
}void add(int u,int v,int w)
{cnt++,edge[cnt].next=h[u],h[u]=cnt,edge[cnt].to=v,edge[cnt].v=w;
}bool bfs()
{int j,p;memset(dis,-1,sizeof(dis));q[1]=1,dis[1]=0;head=0,tail=1;while (head<tail){head++,j=q[head],p=h[j];while (p){if (dis[edge[p].to]<0 && edge[p].v>0)dis[edge[p].to]=dis[j]+1,tail++,q[tail]=edge[p].to;p=edge[p].next;}}if (dis[T]>0)return true;elsereturn false;
}int dfs(int x,int f)
{int w,used=0,i=h[x];if (x==T)return f;while (i){if (edge[i].v && dis[edge[i].to]==dis[x]+1){w=f-used,w=dfs(edge[i].to,min(w,edge[i].v));edge[i].v-=w,edge[i^1].v+=w,used+=w;if (used==f) return f;}i=edge[i].next;}if (!used) dis[x]=-1;return used;
}int main()
{char s[3];int i,u,v,flow;n=read();for (i=1;i<=n;i++){scanf("%s",&s);if (s[0]>='A' && s[0]<='Z')u=s[0]-'A'+1;elseu=s[0]-'a'+27;scanf("%s",&s);if (s[0]>='A' && s[0]<='Z')v=s[0]-'A'+1;elsev=s[0]-'a'+27;flow=read();add(u,v,flow);add(v,u,0);}ans=0;while (bfs())while (sum=dfs(1,0x7fffffff))ans+=sum;printf("%d",ans);return 0;
}

这篇关于BZOJ3396Total flow 水流的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/241193

相关文章

GNSS CTS GNSS Start and Location Flow of Android15

目录 1. 本文概述2.CTS 测试3.Gnss Flow3.1 Gnss Start Flow3.2 Gnss Location Output Flow 1. 本文概述 本来是为了做Android 14 Gnss CTS 的相关环境的搭建和测试,然后在测试中遇到了一些问题,去寻找CTS源码(/cts/tests/tests/location/src/android/locat

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一:卡码网 103. 水流问题 题目链接 题解:DFS 题目二:卡码网 104. 建造最大岛屿 题目链接 题解:DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节,还是选择使用 DFS 来解决这类搜索问题(单纯因为我更熟悉 DFS 一点),今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚

Understanding the GitHub Flow

这里看下Github的入门介绍    --链接 GitHub Flow is a lightweight, branch-based workflow that supports teams and projects where deployments are made regularly. This guide explains how and why GitHub Flow works

图论篇--代码随想录算法训练营第五十二天打卡| 101. 孤岛的总面积,102. 沉没孤岛,103. 水流问题,104.建造最大岛屿

101. 孤岛的总面积 题目链接:101. 孤岛的总面积 题目描述: 给定一个由 1(陆地)和 0(水)组成的矩阵,岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域,且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。 现在你需要计算所有孤岛的总面积,岛屿面积的计算方式为组成岛屿的陆地的总数。 解题思路: 从周边找到陆地,然后通过 dfs或者bfs 将

Versioned Staged Flow-Sensitive Pointer Analysis

VSFS 1.Introduction2.Approach2.1.相关概念2.2.VSFS 3.Evaluation参考文献 1.Introduction 上一篇blog我介绍了目前flow-sensitive pointer analysis常用的SFS算法。相比IFDS-based方法,SFS显著通过稀疏分析提升了效率,但是其内部依旧有许多冗余计算,留下了很大优化空间。 以

Salt Function Flow:深度解析复杂网关编排的优势与实践

系列文章索引: Salt Function Flow 系列文章 在业务流程编排中,处理条件逻辑、并行任务、以及复杂的流程分支是常见的挑战。对于需要高度灵活性和扩展性的项目,Salt Function Flow 提供了强大的网关编排能力,使开发者能够轻松定义和管理复杂的业务流程。本文将深入探讨Salt Function Flow中的复杂网关编排功能,展示其如何通过排他网关、并行执行等功能应对复杂的

Salt Function Flow 系列文章

Salt Function Flow 是一款Java开发、轻量级、内存级的业务流程编排框架,旨在帮助开发者通过函数式编程的方式定义和管理复杂的业务流程。它以高效、灵活的流程处理为核心,适用于多种业务场景,从简单任务自动化到复杂业务逻辑处理。 系列文章: Salt Function Flow:深度研发经验的沉淀,打造轻量级高效流程编排框架 Salt Function Flow:深度解析复杂网关编排

Kotlin 流 Flow

挂起函数可以异步地返回一个值,而对于返回多个值,可以使用流,使用 emit(x) 发射多个值, collect { } 来收集值。 默认 流是冷的,只有 收集(collect) 时才会执行。 1. 流的创建 flow {} 生成流,emit(x) 来发射值;xxx.asFlow() 集合转成Flow;flowOf(1, 2, 3) 生成固定值的流。 1.1 flow {} flow {}

CSS-标准文档流(Normal Flow)

目录 1 定义2 脱离文档流3 相对定位文章参考 1 定义 文档流中:内联元素默认从左到右流,遇到阻碍或者宽度不够自动换行,继续按照从左到右的方式布局。块级元素单独占据一行,并按照从上到下的方式布局。 2 脱离文档流 文档一旦脱离文档流,则元素不再按照文档流的排列方式进行排列,如块级元素脱离文档流后,该块级元素不再接着上个元素从上到下排列,而是成为第一个元素,从顶部开始排列

dfs 解决 部分矩阵洪流/floodfill算法题(水流问题、扫雷游戏、衣橱整理、C++)

文章目录 前言1. 什么是FloodFill问题2. 用什么方法解决FloodFill问题 算法题417.太平洋大西洋水流问题529.扫雷游戏LCR130.衣橱整理 前言 1. 什么是FloodFill问题 一般floodfill问题可以描述为:给定一个二维矩阵,其中每个元素代表一个像素点,并给定一个起始点、目标颜色和填充颜色。问题要求将以起始点为中心,与其相邻且具有相同颜色