UVa 479 Irrigation Flow Rates-育师

题目描述

Mishawaka\texttt{Mishawaka}Mishawaka灌溉公司设计定制管道灌溉系统。系统由若干水井（水源）、若干阀门（可控分流器）和若干喷头（终端）组成，水流仅沿有向边方向流动。每个阀门有一个左出口和一个右出口，通过设置L或R决定水流全部导向左侧或右侧目标。每个水井提供固定的流量（加仑 / 分钟）。对于给定的网络结构和一组阀门设置，需要计算每个喷头最终获得的流量。

输入格式

输入包含多个数据集。每个数据集以一行仅含一个星号*的行结束。数据集的格式如下：

第一行包含三个整数：水井数WWW、喷头数SSS、阀门数VVV。
第二行包含WWW个整数，表示各水井的流量。
接下来的WWW行，每行两个字符串：水井名称和目标组件名称（阀门或喷头）。
接下来的SSS行，每行一个字符串，表示喷头名称。
接下来的VVV行，每行三个字符串：阀门名称、左目标名称、右目标名称。
随后是若干阀门设置记录，每行一个由L和R组成的字符串，长度等于VVV。每组设置记录后可能紧跟下一个设置，也可能跨行。设置记录的结束由一行*标记。

数据集的终止由一行9999 9999 9999表示。

输出格式

对于每个网络，按输入顺序输出标题Irrigation network #X。对于该网络的每组阀门设置，按读入顺序输出标题Valve settings #Y，然后对于每个喷头按输入顺序输出一行：

Sprinkler #i flow is n gallons/min

其中iii为喷头编号，nnn为该喷头的流量。

样例

输入

3 3 7 200 40 73 W1 V1 W2 V2 W3 V3 S1 S2 S3 V1 S1 V4 V2 V4 V5 V3 V5 V7 V4 S1 V6 V5 V6 V7 V6 S1 V7 V7 S2 S3 R L R L R L R L R L R L R L * 2 4 5 100 200 WELL1 VALVE1 WELL2 VALVE2 SPR1 SPR2 SPR3 SPR4 VALVE1 VALVE3 VALVE4 VALVE2 VALVE4 VALVE5 VALVE3 SPR1 SPR2 VALVE4 SPR2 SPR3 VALVE5 SPR3 SPR4 R L R L R L L L R L L R L R L * 9999 9999 9999

输出

Irrigation network #1 Valve settings #1 Sprinkler #1 flow is 240 gallons/min Sprinkler #2 flow is 0 gallons/min Sprinkler #3 flow is 73 gallons/min Valve settings #2 Sprinkler #1 flow is 200 gallons/min Sprinkler #2 flow is 113 gallons/min Sprinkler #3 flow is 0 gallons/min Irrigation network #2 Valve settings #1 Sprinkler #1 flow is 0 gallons/min Sprinkler #2 flow is 300 gallons/min Sprinkler #3 flow is 0 gallons/min Sprinkler #4 flow is 0 gallons/min Valve settings #2 Sprinkler #1 flow is 100 gallons/min Sprinkler #2 flow is 0 gallons/min Sprinkler #3 flow is 200 gallons/min Sprinkler #4 flow is 0 gallons/min Valve settings #3 Sprinkler #1 flow is 100 gallons/min Sprinkler #2 flow is 0 gallons/min Sprinkler #3 flow is 200 gallons/min Sprinkler #4 flow is 0 gallons/min

题目分析

本题的核心是模拟一个有向无环图（DAG\texttt{DAG}DAG）上的流量传播。每个组件（井、阀门、喷头）是图的一个节点。水流只能沿箭头方向流动。每个阀门根据设置只保留一条出边（左或右），而水井的出边固定。喷头没有出边。

对于每一组阀门设置，图的边集确定。水井提供初始流量，这些流量沿边逐步传递到下游节点。由于图是DAG\texttt{DAG}DAG（题意保证水流方向指示，且不会形成环），可以按照拓扑序依次累加流量：当一个节点收到来自所有前驱的流量后，将其全部沿其出边推送给后继节点。最终所有喷头接收到的累计流量即为所求。

因此，解题过程分为两步：

解析输入，建立组件的名称到编号的映射，并记录水井的固定边、阀门的左右边以及喷头列表。
对于每组阀门设置，构建当前的有效边集，计算拓扑序，执行流量累加。

解题思路

数据建模

使用一个结构体Node存储每个组件的类型（井、阀门、喷头）、名称以及相关目标信息。由于组件名称均为字符串，使用unordered_map<string, int>将名称映射到节点编号。在读取过程中动态创建节点，并记录各类型组件的编号列表。

对于水井：存储其固定目标（即出边指向的节点编号）和初始流量。
对于阀门：存储左目标和右目标。
对于喷头：仅需记录编号。

阀门顺序需要固定，因为阀门设置记录的字符序列与输入中阀门出现的顺序一一对应。因此需要按照输入顺序存储阀门编号数组valveIds，并建立阀门节点到其在数组中下标的反向映射valveIdToIdx。

处理单组阀门设置

对于每组设置（一个长度为VVV的L/R字符串）：

构建有效出边数组outEdge，大小为节点总数，初始为−1-1−1。
- 对每个水井节点，outEdge[id] = target。
- 对每个阀门节点，根据设置字符选择左或右目标：outEdge[id] = (c == 'L') ? leftTarget : rightTarget。
- 喷头节点无出边，保持−1-1−1。
计算入度：遍历所有节点，若outEdge[u] != -1，则inDeg[outEdge[u]]++。
初始化流量数组flow，大小为节点总数，全部置000。然后将各水井的初始流量赋值给对应节点。
拓扑排序：将所有入度为000的节点入队（队列使用queue<int>）。依次弹出队首节点uuu：
- 若outEdge[u] != -1，则令v=outEdge[u]v = outEdge[u]v=outEdge[u]，执行flow[v] += flow[u]。
- 然后将inDeg[v]减111，若减后为000，则将vvv入队。
由于图是DAG\texttt{DAG}DAG，此过程能保证所有节点被处理，且每个节点的流量累加其所有前驱的贡献。
输出结果：按照喷头输入顺序，输出各喷头节点的流量值。

正确性保证

拓扑排序的累加过程正确模拟了水流沿边传递的物理过程。因为流量不会凭空产生或消失，每个节点收到的总流量等于其所有前驱流出流量之和，而该节点将其全部流量传递至其后继（若存在）。喷头作为汇点，其流量即为最终输出。

由于每个阀门设置独立，每次均重新构建边和入度，时间复杂度为O((W+V+S)⋅K)O((W+V+S) \cdot K)O((W+V+S)⋅K)，其中KKK为设置总数。节点总数N=W+V+SN = W + V + SN=W+V+S，满足题目限制。

边界情况

可能出现入度为000的孤立节点（例如无出边的喷头或未连接任何水源的阀门），这些节点在拓扑排序中不会影响其他节点，流量保持为000。
阀门设置字符串可能跨多行读入，程序需持续读取直到长度达到VVV。
数据集中可能存在多个水井流量，水井之间不存在汇聚关系，但多个水井可能流向同一节点，此时该节点入度会大于111，累加过程会自动加和。

代码实现

// Irrigation Flow Rates// UVa ID: 479// Verdict: Accepted// Submission Date: 2026-06-27// UVa Run Time: 0.080s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structNode{inttype;// 0: 井, 1: 阀门, 2: 喷头string name;intflowRate;// 仅井有效inttarget;// 仅井有效（固定目标）intleftTarget;// 仅阀门有效intrightTarget;// 仅阀门有效};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intnetworkNum=1;intW,S,V;while(cin>>W>>S>>V){if(W==9999&&S==9999&&V==9999)break;vector<int>wellFlows(W);for(inti=0;i<W;++i)cin>>wellFlows[i];unordered_map<string,int>idOf;vector<Node>nodes;autogetNode=[&](conststring&name)->int{autoit=idOf.find(name);if(it!=idOf.end())returnit->second;Node nd;nd.type=-1;nd.name=name;nd.flowRate=0;nd.target=-1;nd.leftTarget=-1;nd.rightTarget=-1;intid=(int)nodes.size();nodes.push_back(nd);idOf[name]=id;returnid;};vector<string>wellNames(W),wellTargets(W);for(inti=0;i<W;++i){string wName,dest;cin>>wName>>dest;wellNames[i]=wName;wellTargets[i]=dest;intid=getNode(wName);nodes[id].type=0;nodes[id].flowRate=wellFlows[i];}vector<string>sprNames(S);for(inti=0;i<S;++i){string sName;cin>>sName;sprNames[i]=sName;intid=getNode(sName);nodes[id].type=2;}vector<string>valveNames(V),leftDests(V),rightDests(V);for(inti=0;i<V;++i){string vName,lDest,rDest;cin>>vName>>lDest>>rDest;valveNames[i]=vName;leftDests[i]=lDest;rightDests[i]=rDest;intid=getNode(vName);nodes[id].type=1;}intn=(int)nodes.size();// 解析井的目标for(inti=0;i<W;++i){intid=idOf[wellNames[i]];nodes[id].target=idOf[wellTargets[i]];}// 解析阀门的目标，并记录阀门顺序vector<int>valveIds;for(inti=0;i<V;++i){intid=idOf[valveNames[i]];valveIds.push_back(id);nodes[id].leftTarget=idOf[leftDests[i]];nodes[id].rightTarget=idOf[rightDests[i]];}// 记录喷头顺序vector<int>sprinklerIds;for(inti=0;i<S;++i)sprinklerIds.push_back(idOf[sprNames[i]]);// 阀门 id 到其在 valveIds 中下标的映射vector<int>valveIdToIdx(n,-1);for(intidx=0;idx<V;++idx)valveIdToIdx[valveIds[idx]]=idx;cout<<"Irrigation network #"<<networkNum++<<'\n';intsetNum=1;while(true){string setting="";boolended=false;// 读取一个完整的阀门设置（可能由多个 token 组成，也可能是一个连续串）while((int)setting.size()<V){string token;if(!(cin>>token)){ended=true;break;}if(token=="*"){ended=true;break;}setting+=token;}if(ended)break;// 构建当前设置下的有效出边vector<int>outEdge(n,-1);for(inti=0;i<n;++i){if(nodes[i].type==0){// 井outEdge[i]=nodes[i].target;}elseif(nodes[i].type==1){// 阀门intidx=valveIdToIdx[i];charc=setting[idx];outEdge[i]=(c=='L')?nodes[i].leftTarget:nodes[i].rightTarget;}// 喷头无出边}// 计算入度vector<int>inDeg(n,0);for(inti=0;i<n;++i)if(outEdge[i]!=-1)++inDeg[outEdge[i]];// 流量数组，井赋初值，其余为0vector<longlong>flow(n,0);for(inti=0;i<n;++i)if(nodes[i].type==0)flow[i]=nodes[i].flowRate;// 拓扑排序queue<int>q;for(inti=0;i<n;++i)if(inDeg[i]==0)q.push(i);while(!q.empty()){intu=q.front();q.pop();if(outEdge[u]!=-1){intv=outEdge[u];flow[v]+=flow[u];if(--inDeg[v]==0)q.push(v);}}// 输出当前设置的结果cout<<"Valve settings #"<<setNum++<<'\n';for(inti=0;i<S;++i){intid=sprinklerIds[i];cout<<"Sprinkler #"<<(i+1)<<" flow is "<<flow[id]<<" gallons/min\n";}}}return0;}