UVa 12671 Disjoint Water Supply

题目描述

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≤U<V≤C)(1 \le U < V \le C)(1≤U<V≤C)，表示管道连接城市UUU和城市VVV。你可以假设没有两条管道连接同一对城市，并且对于Nlogonia\texttt{Nlogonia}Nlogonia中的每个城市，至少存在一条以该城市为终点的供水路径。

输出格式

对于每个测试用例，输出一行一个整数，表示具有不重叠供水的不同城市对的数量。

题目分析与解题思路

1. 问题本质的理解

首先，我们需要理解“不重叠供水”的严格定义：对于两个不同的城市iii和jjj，存在两条供水路径PiP_iPi​和PjP_jPj​，分别从城市111（Logville\texttt{Logville}Logville）到城市iii和jjj，使得城市111是这两条路径唯一的公共节点。

这意味着：从111到iii的所有可能路径，与从111到jjj的所有可能路径，它们的交集只能是{1}\{1\}{1}。换句话说，不存在一个城市kkk（k≠1k \neq 1k=1），使得kkk同时出现在所有从111到iii的路径和所有从111到jjj的路径上。

2. 图论模型建立

根据题目描述：

• 城市编号从111到CCC，编号越小海拔越高。
• 管道连接(U,V)(U, V)(U,V)满足U<VU < VU<V，说明水只能从高海拔流向低海拔，因此整个供水网络是一个有向无环图（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。

这是因为：

• 如果存在一个节点kkk（k≠1k \neq 1k=1）同时支配iii和jjj，那么从111到iii和从111到jjj的所有路径都必须经过kkk，违反了“不重叠”的条件。
• 反之，如果iii和jjj没有除111以外的公共支配点，那么我们可以找到两条路径，它们只在111处相交。

4. 算法设计

由于图是DAG\texttt{DAG}DAG，计算支配点有相对简单的算法：

1. 计算最近支配点：

   • 对于每个节点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（表示没有支配点或作为根）。
   • 由于节点编号就是拓扑序（u<vu < vu<v），我们可以按编号从小到大计算。

2. 构建支配树：

   • 以idom(v)idom(v)idom(v)作为vvv的父节点，构建一棵树（支配树）。
   • 树根是111（实际上111的父节点设为000）。

3. 判断条件：

   • 在支配树中，两个节点iii和jjj的LCA\texttt{LCA}LCA是111，当且仅当它们位于111的不同子树中。
   • 因此，我们可以通过一次DFS\texttt{DFS}DFS标记每个节点属于111的哪个直接子节点的子树。
   • 如果两个节点标记不同，或者至少有一个是111的直接子节点而另一个不在同一子树，那么它们的LCA\texttt{LCA}LCA就是111。

4. 计数：

   • 首先，城市111与所有其他C−1C-1C−1个城市都满足条件。
   • 然后，对于其他城市对(i,j)(i, j)(i,j)（i,j≥2i, j \ge 2i,j≥2），如果它们属于不同的子树，则计数加一。

5. 复杂度分析

• 计算支配点：O(C+P)O(C + P)O(C+P)。
• 构建支配树并进行DFS\texttt{DFS}DFS标记：O(C)O(C)O(C)。
• 枚举城市对：O(C2)O(C^2)O(C2)，但C≤1000C \le 1000C≤1000，C2=106C^2 = 10^6C2=106可接受。
• 总复杂度：O(C2+P)O(C^2 + P)O(C2+P)，对于题目限制是可行的。

代码实现

// Disjoint Water Supply// UVa ID: 12671// Verdict: Accepted// Submission Date: 2026-01-01// UVa Run Time: 0.040s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXC=1005;vector<int>graph[MAXC];// 有向图vector<int>pred[MAXC];// 前驱intidom[MAXC];// 最近支配点vector<int>domTree[MAXC];// 支配树// 快速计算最近支配点voidcomputeDominators(intC){// 初始化for(inti=1;i<=C;i++){idom[i]=-1;domTree[i].clear();}idom[1]=0;// 1 的支配点是 0（表示没有支配点或根）// 按拓扑序处理（编号顺序就是拓扑序）for(intv=2;v<=C;v++){if(pred[v].empty()){idom[v]=1;continue;}// 找所有前驱的公共最近支配点intcommon=pred[v][0];for(size_t i=1;i<pred[v].size();i++){inta=common,b=pred[v][i];// 找 a 和 b 在支配树中的 LCAwhile(a!=b){if(a>b)a=idom[a];elseb=idom[b];}common=a;}idom[v]=common;}// 构建支配树for(inti=1;i<=C;i++){if(idom[i]>0){domTree[idom[i]].push_back(i);}}}// DFS 标记子树voiddfsMark(intu,introot,vector<int>&mark){mark[u]=root;for(intv:domTree[u]){dfsMark(v,root,mark);}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intC,P;while(cin>>C>>P){// 初始化for(inti=1;i<=C;i++){graph[i].clear();pred[i].clear();}// 读入图for(inti=0;i<P;i++){intU,V;cin>>U>>V;graph[U].push_back(V);pred[V].push_back(U);}// 计算支配点computeDominators(C);// 方法：对于支配树中 1 的每个直接子节点，标记它的整个子树// 如果两个节点在不同的子树中，或者一个是 1，那么它们就是 disjoint 的vector<int>subtreeRoot(C+1,0);// 标记每个节点的子树for(intchild:domTree[1]){dfsMark(child,child,subtreeRoot);}// 1 本身标记为 0subtreeRoot[1]=0;// 计算答案intcount=0;// 1 与所有其他城市count+=(C-1);// 其他城市对for(inti=2;i<=C;i++){for(intj=i+1;j<=C;j++){// 如果 i 和 j 在不同的子树中，或者至少有一个是 1 的直接子节点且另一个不在同一子树if(subtreeRoot[i]!=subtreeRoot[j]){count++;}}}cout<<count<<endl;}return0;}

总结

本题的关键在于将“不重叠供水”的条件转化为图论中的支配点问题。通过构建支配树，我们可以高效地判断两个城市是否满足条件。算法的主要步骤包括计算最近支配点、构建支配树、标记子树以及枚举计数。由于城市数CCC不超过100010001000，O(C2+P)O(C^2 + P)O(C2+P)的复杂度完全可行。

此解法充分利用了DAG\texttt{DAG}DAG的性质和支配点的理论，是图论知识在实际问题中的一个典型应用。