博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷 P2936 [USACO09JAN]全流Total Flow
阅读量:6381 次
发布时间:2019-06-23

本文共 4127 字,大约阅读时间需要 13 分钟。

题目描述

Farmer John always wants his cows to have enough water and thus has made a map of the N (1 <= N <= 700) water pipes on the farm that connect the well to the barn. He was surprised to find a wild mess of different size pipes connected in an apparently haphazard way. He wants to calculate the flow through the pipes.

Two pipes connected in a row allow water flow that is the minimum of the values of the two pipe's flow values. The example of a pipe with flow capacity 5 connecting to a pipe of flow capacity 3 can be reduced logically to a single pipe of flow capacity 3:

+---5---+---3---+    ->    +---3---+

Similarly, pipes in parallel let through water that is the sum of their flow capacities:

+---5---+

---+       +---    ->    +---8---+

+---3---+

Finally, a pipe that connects to nothing else can be removed; it contributes no flow to the final overall capacity:

+---5---+

---+               ->    +---3---+

+---3---+--

All the pipes in the many mazes of plumbing can be reduced using these ideas into a single total flow capacity.

Given a map of the pipes, determine the flow capacity between the well (A) and the barn (Z).

Consider this example where node names are labeled with letters:

+-----------6-----------+

A+---3---+B                      +Z

+---3---+---5---+---4---+

C       D

Pipe BC and CD can be combined:

+-----------6-----------+

A+---3---+B                      +Z

+-----3-----+-----4-----+

D Then BD and DZ can be combined:

+-----------6-----------+

A+---3---+B                      +Z

+-----------3-----------+

Then two legs of BZ can be combined:

B A+---3---+---9---+Z

Then AB and BZ can be combined to yield a net capacity of 3:

A+---3---+Z

Write a program to read in a set of pipes described as two endpoints and then calculate the net flow capacity from 'A' to 'Z'. All

networks in the test data can be reduced using the rules here.

Pipe i connects two different nodes a_i and b_i (a_i in range

'A-Za-z'; b_i in range 'A-Za-z') and has flow F_i (1 <= F_i <= 1,000). Note that lower- and upper-case node names are intended to be treated as different.

The system will provide extra test case feedback for your first 50 submissions.

约翰总希望他的奶牛有足够的水喝,因此他找来了农场的水管地图,想算算牛棚得到的水的 总流量.农场里一共有N根水管.约翰发现水管网络混乱不堪,他试图对其进行简 化.他简化的方式是这样的:

两根水管串联,则可以用较小流量的那根水管代替总流量.

两根水管并联,则可以用流量为两根水管流量和的一根水管代替它们

当然,如果存在一根水管一端什么也没有连接,可以将它移除.

请写个程序算出从水井A到牛棚Z的总流量.数据保证所有输入的水管网络都可以用上述方法 简化.

输入输出格式

输入格式:

  • Line 1: A single integer: N

  • Lines 2..N + 1: Line i+1 describes pipe i with two letters and an integer, all space-separated: a_i, b_i, and F_i

 

输出格式:

  • Line 1: A single integer that the maximum flow from the well ('A') to the barn ('Z')

 

输入输出样例

输入样例#1:
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
输出样例#1:
3

吐槽//或者这次该叫反思感想什么的吧

  不知怎么了,可能是连续一周每天4.5h的睡眠造成的吧。难题根本不想看不想写,就写道裸题放松一下吧。国赛将近,亚历山大啊……

解题思路

  最大流裸题,套板子吧。不过这题字符输入方法值得学习。

源代码

#include
#include
#include
#include
int n,m;struct Edge{ int next,to,flow;}e[10010]={
0};int cnt=2,head[500]={
0};void add(int u,int v,int f){ e[cnt]={head[u],v,f}; head[u]=cnt++; e[cnt]={head[v],u,0}; head[v]=cnt++;}int s=1,t=26;int dis[500]={
0};bool bfs(){ std::queue
q; memset(dis,0,sizeof(dis)); q.push(s); dis[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]||!e[i].flow) continue; dis[v]=dis[u]+1; q.push(v); } } return dis[t]!=0;}int dfs(int u,int f){ if(f==0||u==t) return f; int flow_sum=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]!=dis[u]+1||!e[i].flow) continue; int temp=dfs(v,std::min(e[i].flow,f-flow_sum)); e[i].flow-=temp; e[i^1].flow+=temp; flow_sum+=temp; if(flow_sum>=f) break; } if(flow_sum==0) dis[u]=-1; return flow_sum;}int dinic(){ int ans=0; while(bfs()) { while(int temp=dfs(s,0x7fffffff)) ans+=temp; } return ans;}int main(){ scanf("%d",&n); for(int i=1,f;i<=n;i++) { char u[2],v[2]; scanf("%s%s%d",u,v,&f); add(u[0]-'A'+1,v[0]-'A'+1,f); } printf("%d\n",dinic()); return 0;}

 

转载地址:http://tfhqa.baihongyu.com/

你可能感兴趣的文章
Linux vi/vim编辑器常用命令与用法总结
查看>>
对于 url encode decode js 和 c# 有差异
查看>>
mysql 修改列为not null报错Invalid use of NULL value
查看>>
epoll源码分析
查看>>
朱晔和你聊Spring系列S1E4:灵活但不算好用的Spring MVC
查看>>
Java使用Try with resources自动关闭资源
查看>>
china-pub十一周年庆,多重优惠隆重登场,千万别错过哟!
查看>>
HDU 3068 最长回文(manacher算法)
查看>>
二叉树
查看>>
手把手教你如何安装水晶易表——靠谱的安装教程
查看>>
Python单例模式(Singleton)的N种实现
查看>>
221. Maximal Square
查看>>
MySQL基础
查看>>
LeetCode35.搜索插入位置 JavaScript
查看>>
5个让人赞不绝口的微信小程序,拒绝占用手机内存!
查看>>
Spring Security整合KeyCloak保护Rest API
查看>>
POS概述
查看>>
containerd发布了CRI修复程序和CVE-2019-5736更新的runc
查看>>
WEB前端开发的思考与感悟
查看>>
微信自动跳转浏览器打开APP(APK)下载链接
查看>>