题目描述Nlogonia\texttt{Nlogonia}Nlogonia是一个由位于大山上的若干城市组成的女王国度。首都是Logville\texttt{Logville}Logville城市111位于山顶。Logville\texttt{Logville}Logville有一个巨大且形状完美的圆形湖泊这是整个王国唯一拥有可饮用水的湖泊因此用于供应所有城市。Nlogonia\texttt{Nlogonia}Nlogonia中的一些城市通过水管连接以便分配水。由于没有水泵每根水管利用重力将水从一个城市输送到海拔更低的另一个城市。一条供水路径是一系列按海拔降序排列的城市从Logville\texttt{Logville}Logville开始并且序列中每对连续城市之间都有水管连接。当且仅当存在两条供水路径每条路径分别以两个城市为终点并且Logville\texttt{Logville}Logville是唯一同时出现在两条路径中的城市时这两个城市具有不重叠供水。注意Logville\texttt{Logville}Logville本身与每个其他城市都具有不重叠供水。女王下令调查整个王国当前供水不重叠的状况。作为女王宫廷中最聪明的顾问你需要帮助计算具有不重叠供水的不同城市对的数量。输入格式输入文件包含多个测试用例。每个测试用例描述如下第一行包含两个整数CCC(2≤C≤1000)(2 \le C \le 1000)(2≤C≤1000)和PPP(1≤P≤105)(1 \le P \le 10^5)(1≤P≤105)分别代表Nlogonia\texttt{Nlogonia}Nlogonia中的城市数量和供水管道数量。城市用111到CCC的不同整数标识按海拔严格降序排列没有两个城市海拔相同Logville\texttt{Logville}Logville是城市111。接下来的PPP行每行描述一条管道包含两个整数UUU和VVV(1≤UV≤C)(1 \le U V \le C)(1≤UV≤C)表示管道连接城市UUU和城市VVV。你可以假设没有两条管道连接同一对城市并且对于Nlogonia\texttt{Nlogonia}Nlogonia中的每个城市至少存在一条以该城市为终点的供水路径。输出格式对于每个测试用例输出一行一个整数表示具有不重叠供水的不同城市对的数量。题目分析与解题思路1. 问题本质的理解首先我们需要理解“不重叠供水”的严格定义对于两个不同的城市iii和jjj存在两条供水路径PiP_iPi​和PjP_jPj​分别从城市111Logville\texttt{Logville}Logville到城市iii和jjj使得城市111是这两条路径唯一的公共节点。这意味着从111到iii的所有可能路径与从111到jjj的所有可能路径它们的交集只能是{1}\{1\}{1}。换句话说不存在一个城市kkkk≠1k \neq 1k1使得kkk同时出现在所有从111到iii的路径和所有从111到jjj的路径上。2. 图论模型建立根据题目描述城市编号从111到CCC编号越小海拔越高。管道连接(U,V)(U, V)(U,V)满足UVU VUV说明水只能从高海拔流向低海拔因此整个供水网络是一个有向无环图DAG\texttt{DAG}DAG。从城市111到每个城市至少有一条路径因此以111为根整个图是连通的在可达意义上。题目要求我们计算所有城市对(i,j)(i, j)(i,j)i≠ji \neq jij中满足“不重叠供水”的对数。3. 转化为支配点问题在图论中如果从源点sss到节点vvv的所有路径都必须经过节点ddd那么ddd被称为vvv的支配点dominator\texttt{dominator}dominator。特别地最近支配点immediate dominator\texttt{immediate dominator}immediate dominator是指除vvv自身外离vvv最近的支配点。在本题中源点是城市111。对于城市vvv它的支配点集合就是从111到vvv的所有路径上的公共节点集合。两个城市iii和jjj具有不重叠供水当且仅当它们没有除111以外的公共支配点。也就是说在支配树中iii和jjj的最近公共祖先LCA\texttt{LCA}LCA是111。这是因为如果存在一个节点kkkk≠1k \neq 1k1同时支配iii和jjj那么从111到iii和从111到jjj的所有路径都必须经过kkk违反了“不重叠”的条件。反之如果iii和jjj没有除111以外的公共支配点那么我们可以找到两条路径它们只在111处相交。4. 算法设计由于图是DAG\texttt{DAG}DAG计算支配点有相对简单的算法计算最近支配点对于每个节点vvv设其前驱节点集合为pred(v)pred(v)pred(v)即所有满足(u,v)(u, v)(u,v)是边的uuu。节点vvv的最近支配点idom(v)idom(v)idom(v)是pred(v)pred(v)pred(v)中所有节点的最近支配点在支配树中的LCA\texttt{LCA}LCA。特别地idom(1)0idom(1) 0idom(1)0表示没有支配点或作为根。由于节点编号就是拓扑序uvu vuv我们可以按编号从小到大计算。构建支配树以idom(v)idom(v)idom(v)作为vvv的父节点构建一棵树支配树。树根是111实际上111的父节点设为000。判断条件在支配树中两个节点iii和jjj的LCA\texttt{LCA}LCA是111当且仅当它们位于111的不同子树中。因此我们可以通过一次DFS\texttt{DFS}DFS标记每个节点属于111的哪个直接子节点的子树。如果两个节点标记不同或者至少有一个是111的直接子节点而另一个不在同一子树那么它们的LCA\texttt{LCA}LCA就是111。计数首先城市111与所有其他C−1C-1C−1个城市都满足条件。然后对于其他城市对(i,j)(i, j)(i,j)i,j≥2i, j \ge 2i,j≥2如果它们属于不同的子树则计数加一。5. 复杂度分析计算支配点O(CP)O(C P)O(CP)。构建支配树并进行DFS\texttt{DFS}DFS标记O(C)O(C)O(C)。枚举城市对O(C2)O(C^2)O(C2)但C≤1000C \le 1000C≤1000C2106C^2 10^6C2106可接受。总复杂度O(C2P)O(C^2 P)O(C2P)对于题目限制是可行的。代码实现// Disjoint Water Supply// UVa ID: 12671// Verdict: Accepted// Submission Date: 2026-01-01// UVa Run Time: 0.040s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXC1005;vectorintgraph[MAXC];// 有向图vectorintpred[MAXC];// 前驱intidom[MAXC];// 最近支配点vectorintdomTree[MAXC];// 支配树// 快速计算最近支配点voidcomputeDominators(intC){// 初始化for(inti1;iC;i){idom[i]-1;domTree[i].clear();}idom[1]0;// 1 的支配点是 0表示没有支配点或根// 按拓扑序处理编号顺序就是拓扑序for(intv2;vC;v){if(pred[v].empty()){idom[v]1;continue;}// 找所有前驱的公共最近支配点intcommonpred[v][0];for(size_t i1;ipred[v].size();i){intacommon,bpred[v][i];// 找 a 和 b 在支配树中的 LCAwhile(a!b){if(ab)aidom[a];elsebidom[b];}commona;}idom[v]common;}// 构建支配树for(inti1;iC;i){if(idom[i]0){domTree[idom[i]].push_back(i);}}}// DFS 标记子树voiddfsMark(intu,introot,vectorintmark){mark[u]root;for(intv:domTree[u]){dfsMark(v,root,mark);}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intC,P;while(cinCP){// 初始化for(inti1;iC;i){graph[i].clear();pred[i].clear();}// 读入图for(inti0;iP;i){intU,V;cinUV;graph[U].push_back(V);pred[V].push_back(U);}// 计算支配点computeDominators(C);// 方法对于支配树中 1 的每个直接子节点标记它的整个子树// 如果两个节点在不同的子树中或者一个是 1那么它们就是 disjoint 的vectorintsubtreeRoot(C1,0);// 标记每个节点的子树for(intchild:domTree[1]){dfsMark(child,child,subtreeRoot);}// 1 本身标记为 0subtreeRoot[1]0;// 计算答案intcount0;// 1 与所有其他城市count(C-1);// 其他城市对for(inti2;iC;i){for(intji1;jC;j){// 如果 i 和 j 在不同的子树中或者至少有一个是 1 的直接子节点且另一个不在同一子树if(subtreeRoot[i]!subtreeRoot[j]){count;}}}coutcountendl;}return0;}总结本题的关键在于将“不重叠供水”的条件转化为图论中的支配点问题。通过构建支配树我们可以高效地判断两个城市是否满足条件。算法的主要步骤包括计算最近支配点、构建支配树、标记子树以及枚举计数。由于城市数CCC不超过100010001000O(C2P)O(C^2 P)O(C2P)的复杂度完全可行。此解法充分利用了DAG\texttt{DAG}DAG的性质和支配点的理论是图论知识在实际问题中的一个典型应用。