题目描述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_mapstring, 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的节点入队队列使用queueint。依次弹出队首节点uuu若outEdge[u] ! -1则令voutEdge[u]v outEdge[u]voutEdge[u]执行flow[v] flow[u]。然后将inDeg[v]减111若减后为000则将vvv入队。由于图是DAG\texttt{DAG}DAG此过程能保证所有节点被处理且每个节点的流量累加其所有前驱的贡献。输出结果按照喷头输入顺序输出各喷头节点的流量值。正确性保证拓扑排序的累加过程正确模拟了水流沿边传递的物理过程。因为流量不会凭空产生或消失每个节点收到的总流量等于其所有前驱流出流量之和而该节点将其全部流量传递至其后继若存在。喷头作为汇点其流量即为最终输出。由于每个阀门设置独立每次均重新构建边和入度时间复杂度为O((WVS)⋅K)O((WVS) \cdot K)O((WVS)⋅K)其中KKK为设置总数。节点总数NWVSN W V SNWVS满足题目限制。边界情况可能出现入度为000的孤立节点例如无出边的喷头或未连接任何水源的阀门这些节点在拓扑排序中不会影响其他节点流量保持为000。阀门设置字符串可能跨多行读入程序需持续读取直到长度达到VVV。数据集中可能存在多个水井流量水井之间不存在汇聚关系但多个水井可能流向同一节点此时该节点入度会大于111累加过程会自动加和。代码实现// Irrigation Flow Rates// UVa ID: 479// Verdict: Accepted// Submission Date: 2026-06-27// UVa Run Time: 0.080s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structNode{inttype;// 0: 井, 1: 阀门, 2: 喷头string name;intflowRate;// 仅井有效inttarget;// 仅井有效固定目标intleftTarget;// 仅阀门有效intrightTarget;// 仅阀门有效};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intnetworkNum1;intW,S,V;while(cinWSV){if(W9999S9999V9999)break;vectorintwellFlows(W);for(inti0;iW;i)cinwellFlows[i];unordered_mapstring,intidOf;vectorNodenodes;autogetNode[](conststringname)-int{autoitidOf.find(name);if(it!idOf.end())returnit-second;Node nd;nd.type-1;nd.namename;nd.flowRate0;nd.target-1;nd.leftTarget-1;nd.rightTarget-1;intid(int)nodes.size();nodes.push_back(nd);idOf[name]id;returnid;};vectorstringwellNames(W),wellTargets(W);for(inti0;iW;i){string wName,dest;cinwNamedest;wellNames[i]wName;wellTargets[i]dest;intidgetNode(wName);nodes[id].type0;nodes[id].flowRatewellFlows[i];}vectorstringsprNames(S);for(inti0;iS;i){string sName;cinsName;sprNames[i]sName;intidgetNode(sName);nodes[id].type2;}vectorstringvalveNames(V),leftDests(V),rightDests(V);for(inti0;iV;i){string vName,lDest,rDest;cinvNamelDestrDest;valveNames[i]vName;leftDests[i]lDest;rightDests[i]rDest;intidgetNode(vName);nodes[id].type1;}intn(int)nodes.size();// 解析井的目标for(inti0;iW;i){intididOf[wellNames[i]];nodes[id].targetidOf[wellTargets[i]];}// 解析阀门的目标并记录阀门顺序vectorintvalveIds;for(inti0;iV;i){intididOf[valveNames[i]];valveIds.push_back(id);nodes[id].leftTargetidOf[leftDests[i]];nodes[id].rightTargetidOf[rightDests[i]];}// 记录喷头顺序vectorintsprinklerIds;for(inti0;iS;i)sprinklerIds.push_back(idOf[sprNames[i]]);// 阀门 id 到其在 valveIds 中下标的映射vectorintvalveIdToIdx(n,-1);for(intidx0;idxV;idx)valveIdToIdx[valveIds[idx]]idx;coutIrrigation network #networkNum\n;intsetNum1;while(true){string setting;boolendedfalse;// 读取一个完整的阀门设置可能由多个 token 组成也可能是一个连续串while((int)setting.size()V){string token;if(!(cintoken)){endedtrue;break;}if(token*){endedtrue;break;}settingtoken;}if(ended)break;// 构建当前设置下的有效出边vectorintoutEdge(n,-1);for(inti0;in;i){if(nodes[i].type0){// 井outEdge[i]nodes[i].target;}elseif(nodes[i].type1){// 阀门intidxvalveIdToIdx[i];charcsetting[idx];outEdge[i](cL)?nodes[i].leftTarget:nodes[i].rightTarget;}// 喷头无出边}// 计算入度vectorintinDeg(n,0);for(inti0;in;i)if(outEdge[i]!-1)inDeg[outEdge[i]];// 流量数组井赋初值其余为0vectorlonglongflow(n,0);for(inti0;in;i)if(nodes[i].type0)flow[i]nodes[i].flowRate;// 拓扑排序queueintq;for(inti0;in;i)if(inDeg[i]0)q.push(i);while(!q.empty()){intuq.front();q.pop();if(outEdge[u]!-1){intvoutEdge[u];flow[v]flow[u];if(--inDeg[v]0)q.push(v);}}// 输出当前设置的结果coutValve settings #setNum\n;for(inti0;iS;i){intidsprinklerIds[i];coutSprinkler #(i1) flow is flow[id] gallons/min\n;}}}return0;}总结本题的关键点在于正确解析自由格式的输入动态构建节点映射。利用拓扑排序处理DAG\texttt{DAG}DAG上的流量累加避免递归或遍历所有路径。每次阀门设置独立需重新构建图并进行拓扑排序复杂度线性于节点数和设置数。注意阀门设置的读取可能跨行需要持续拼接直到长度满足。本题技巧使用unordered_map实现字符串到编号的快速映射。使用队列实现拓扑排序简洁高效。流量累加使用long long防止溢出实际题目数据可能较大。通过本题可以掌握模拟 DAG 流传播的一般方法以及处理多组测试数据和灵活输入格式的能力。