UVa 1018 Building Bridges

题目描述

New Altonville\texttt{New Altonville}New Altonville市议会计划建造一个桥梁系统，连接市中心的所有建筑，以便人们可以在不走到户外的情况下从一栋建筑走到另一栋建筑。你需要编写一个程序来帮助确定最佳的桥梁配置。

New Altonville\texttt{New Altonville}New Altonville被布置为一个正方形网格。每栋建筑占据一个或多个相连的方格。两个角部接触的占用的方格被认为是同一栋建筑，不需要桥梁。桥梁只能建在形成方格边缘的网格线上。每座桥必须是直线建造，并且必须恰好连接两栋建筑。

对于给定的一组建筑，你需要找到连接所有建筑所需的最少桥梁数量。如果不可能，则找到使不连通建筑组数量最小化的解决方案。在桥梁数量相同的可能解决方案中，选择使桥梁长度总和最小的方案（长度以网格尺寸的倍数计量）。两座桥可以交叉，但此时它们被认为是位于不同层面，不会提供从一座桥到另一座桥的连接。

输入格式

输入数据集描述了几个矩形城市。每个城市描述以一行包含两个整数rrr和ccc开头，表示城市南北和东西方向的网格长度尺寸（1≤r≤1001 \le r \le 1001≤r≤100，1≤c≤1001 \le c \le 1001≤c≤100）。随后是恰好rrr行，每行由ccc个井号（#）和点号（.）字符组成。每个字符对应网格中的一个方格。井号表示建筑占用的方格，点号表示未被占用的方格。

最后一个城市的输入数据后，是一行包含两个零的行。

输出格式

对于每个城市描述，按如下所示打印两行或三行输出。第一行是城市编号。如果城市的建筑少于两栋，第二行是句子No bridges are needed.。如果城市有两栋或更多建筑但没有桥梁可以连接，第二行是句子No bridges are possible.。否则，第二行是N bridges of total length L，其中NNN是最佳方案中的桥梁数量，LLL是桥梁长度总和。（如果NNN为111，使用单词bridge而不是bridges。）如果解决方案留下两个或更多不连通的建筑组，打印第三行，包含不连通组的数量。

案例之间打印一个空行。使用示例中显示的输出格式。

样例

输入

3 5 #...# ..#.. #...# 3 5 ##... ..... ....# 3 5 #.### #.#.# ###.# 3 5 #.#.. ..... ....# 0 0

输出

City 1 4 bridges of total length 4 City 2 No bridges are possible. 2 disconnected groups City 3 No bridges are needed. City 4 1 bridge of total length 1 2 disconnected groups

题目分析

本题的核心是将网格中的建筑识别为连通块，然后在建筑之间建立桥梁，使得整个图连通（或连通分量数最少），同时优先最小化桥梁数量，其次最小化桥梁总长度。

关键点

1. 建筑识别：两个占用的方格如果角部接触（即888方向相邻），则属于同一建筑。因此需要使用888方向的洪水填充（DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS）来标记每个连通块，并为每个建筑分配唯一的编号。

2. 桥梁的可行性判断：两栋建筑之间可以建造桥梁，当且仅当存在一个格子属于建筑AAA和一个格子属于建筑BBB，使得这两个格子的行差≤1\le 1≤1或列差≤1\le 1≤1。这是因为桥梁必须建在网格线上，而两个格子行相邻或列相邻意味着它们共享一条网格线边界。

3. 桥梁长度的计算：

   • 如果两个格子的行差≤1\le 1≤1，桥梁长度为它们的列差减去111（即∣c1−c2∣−1|c_1 - c_2| - 1∣c1​−c2​∣−1）。
   • 如果两个格子的列差≤1\le 1≤1，桥梁长度为它们的行差减去111（即∣r1−r2∣−1|r_1 - r_2| - 1∣r1​−r2​∣−1）。
   • 对于一对建筑，可能存在多对格子满足条件，取所有可能桥梁长度的最小值作为该建筑对的最短桥梁长度。

4. 优化目标：需要找到一个边集，使得：

   • 优先最小化不连通分量的数量（即尽可能多的建筑被连接）。
   • 在不连通分量数量最小的前提下，最小化使用的桥梁数量。
   • 在桥梁数量相同的前提下，最小化桥梁总长度。

   这等价于：在由建筑为顶点、可行桥梁为边的图中，找出一个最小生成森林（按桥梁长度排序的Kruskal\texttt{Kruskal}Kruskal算法），因为Kruskal\texttt{Kruskal}Kruskal在无负权边的情况下，会优先选择最短的边，自然地使每个连通分量内的总长度最小，同时使用的边数也是该分量最小生成树的边数（即顶点数减111）。

5. 特殊情况：

   • 如果整个城市只有一个建筑，不需要桥梁。
   • 如果没有任何可行的桥梁，输出No bridges are possible.，并输出不连通组数（即建筑数量）。
   • 如果桥梁数量为111，输出时使用单数形式bridge。

解题思路

步骤一：标记建筑（连通块）

使用888方向DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS遍历网格，为每个#格子分配建筑编号。同时记录每个建筑包含的所有格子坐标，以及建筑的行列范围（用于后续可能的剪枝，但本题直接枚举所有格子对即可）。

步骤二：枚举所有可行的桥梁

对于每对不同的建筑iii和jjj，枚举它们的所有格子对(p,q)(p, q)(p,q)，其中ppp属于建筑iii，qqq属于建筑jjj。检查是否满足行差≤1\le 1≤1或列差≤1\le 1≤1：

• 若∣rp−rq∣≤1|r_p - r_q| \le 1∣rp​−rq​∣≤1，则桥梁长度为∣cp−cq∣−1|c_p - c_q| - 1∣cp​−cq​∣−1。
• 若∣cp−cq∣≤1|c_p - c_q| \le 1∣cp​−cq​∣≤1，则桥梁长度为∣rp−rq∣−1|r_p - r_q| - 1∣rp​−rq​∣−1。

取所有格子对的最小值作为建筑对(i,j)(i, j)(i,j)的最短桥梁长度。如果最小值存在（即至少有一对格子满足条件），则将该边加入候选边集。

步骤三：构建最小生成森林

将候选边按桥梁长度升序排序。初始化并查集，每个建筑自成一个集合。遍历排序后的边，如果当前边连接的两个建筑属于不同集合，则合并它们，并累加桥梁总长度和桥梁数量。这个过程就是Kruskal\texttt{Kruskal}Kruskal算法，它会自动生成一个最小生成森林，其中每个连通分量内部的总长度最小。

步骤四：输出结果

• 统计并查集中集合的数量（即不连通的建筑组数）。
• 如果桥梁数量为000：
  • 若建筑总数≥2\ge 2≥2，输出No bridges are possible.，并输出不连通组数。
  • 若建筑总数<2< 2<2，这种情况在之前已单独处理。
• 否则，输出桥梁数量和总长度，如果存在多个连通组，还要输出组数。

复杂度分析

• 建筑数量最多为r×c≤104r \times c \le 10^4r×c≤104，但实际建筑数量通常远小于此。
• 枚举所有建筑对并枚举格子对，最坏情况下每个建筑只有一个格子（即所有#都不相邻），格子对的数量为O(K2)O(K^2)O(K2)，其中KKK为#的数量。KKK最大为10410^4104，K2=108K^2 = 10^8K2=108，在时限内勉强可行（实际数据不会达到最坏情况）。
• 并查集操作近似O(α(K))O(\alpha(K))O(α(K))。
• 总复杂度：O(K2log⁡K)O(K^2 \log K)O(K2logK)，其中KKK为#的数量。

代码实现

// Building Bridges// UVa ID: 1018// Verdict: Accepted// Submission Date: 2026-06-14// UVa Run Time: 0.050s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=105;constintMAXB=10005;intr,c;chargrid[MAXN][MAXN];intcomp[MAXN][MAXN];intcompCount;intdx[8]={-1,-1,-1,0,0,1,1,1};intdy[8]={-1,0,1,-1,1,-1,0,1};structBuilding{intminRow,maxRow,minCol,maxCol;vector<pair<int,int>>cells;}bld[MAXB];voidfloodFill(intx,inty,intid){if(x<0||x>=r||y<0||y>=c)return;if(grid[x][y]!='#')return;if(comp[x][y]!=-1)return;comp[x][y]=id;bld[id].cells.push_back({x,y});bld[id].minRow=min(bld[id].minRow,x);bld[id].maxRow=max(bld[id].maxRow,x);bld[id].minCol=min(bld[id].minCol,y);bld[id].maxCol=max(bld[id].maxCol,y);for(intd=0;d<8;d++)floodFill(x+dx[d],y+dy[d],id);}structBridge{intu,v,len;booloperator<(constBridge&other)const{returnlen<other.len;}};vector<Bridge>bridges;intparent[MAXB];intfindSet(intx){if(parent[x]!=x)parent[x]=findSet(parent[x]);returnparent[x];}boolunionSet(intx,inty){intrx=findSet(x),ry=findSet(y);if(rx==ry)returnfalse;parent[rx]=ry;returntrue;}voidsolve(intcityNum){memset(comp,-1,sizeof(comp));compCount=0;for(inti=0;i<MAXB;i++){bld[i].minRow=bld[i].minCol=1e9;bld[i].maxRow=bld[i].maxCol=-1e9;bld[i].cells.clear();}for(inti=0;i<r;i++)for(intj=0;j<c;j++)if(grid[i][j]=='#'&&comp[i][j]==-1)floodFill(i,j,compCount++);if(compCount<2){printf("City %d\nNo bridges are needed.\n",cityNum);return;}bridges.clear();for(inti=0;i<compCount;i++){for(intj=i+1;j<compCount;j++){intminLen=1e9;for(auto&cellA:bld[i].cells){for(auto&cellB:bld[j].cells){intdr=abs(cellA.first-cellB.first);intdc=abs(cellA.second-cellB.second);if(dr<=1)minLen=min(minLen,dc-1);if(dc<=1)minLen=min(minLen,dr-1);}}if(minLen<1e9)bridges.push_back({i,j,minLen});}}sort(bridges.begin(),bridges.end());for(inti=0;i<compCount;i++)parent[i]=i;inttotalLen=0,used=0;for(auto&b:bridges)if(unionSet(b.u,b.v)){totalLen+=b.len;used++;}intgroups=0;for(inti=0;i<compCount;i++)if(findSet(i)==i)groups++;if(used==0){printf("City %d\nNo bridges are possible.\n",cityNum);if(groups>1)printf("%d disconnected groups\n",groups);}else{printf("City %d\n",cityNum);if(used==1)printf("1 bridge of total length %d\n",totalLen);elseprintf("%d bridges of total length %d\n",used,totalLen);if(groups>1)printf("%d disconnected groups\n",groups);}}intmain(){intcityNum=0;while(scanf("%d %d",&r,&c)==2){if(r==0&&c==0)break;for(inti=0;i<r;i++)scanf("%s",grid[i]);if(cityNum>0)printf("\n");solve(++cityNum);}return0;}

总结

本题综合考察了以下几个关键知识点：

1. 连通块标记：使用888方向DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS将角部接触的方格合并为同一建筑，这是处理网格连通性问题的基础技巧。

2. 几何建模：将建筑抽象为顶点，可行桥梁抽象为带权边，将原问题转化为图论中的最小生成森林问题。这里的关键在于正确计算桥梁长度：需要考虑建筑的边界，桥梁长度等于两个建筑相邻边之间的网格线距离，而不是简单的曼哈顿距离。

3. 多目标优化：优先最小化不连通分量数（通过最小生成森林自动实现），其次最小化桥梁数量（边数），最后最小化总长度（Kruskal\texttt{Kruskal}Kruskal按长度排序）。由于每条桥梁长度均为正数，Kruskal\texttt{Kruskal}Kruskal自然地在连通分量数固定的前提下使用了最少的边数（即顶点数减111）。

4. 实现细节：

   • 注意桥梁数量为111时的单复数形式。
   • 每个案例之间输出一个空行，但最后一个案例后不能有多余空行。
   • 对于没有可行桥梁的情况，需要输出不连通组数（即建筑数量）。

通过本题，可以加深对图论模型构建、并查集应用以及网格问题处理技巧的理解。