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≤1001≤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题目分析本题的核心是将网格中的建筑识别为连通块然后在建筑之间建立桥梁使得整个图连通或连通分量数最少同时优先最小化桥梁数量其次最小化桥梁总长度。关键点建筑识别两个占用的方格如果角部接触即888方向相邻则属于同一建筑。因此需要使用888方向的洪水填充DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS来标记每个连通块并为每个建筑分配唯一的编号。桥梁的可行性判断两栋建筑之间可以建造桥梁当且仅当存在一个格子属于建筑AAA和一个格子属于建筑BBB使得这两个格子的行差≤1\le 1≤1或列差≤1\le 1≤1。这是因为桥梁必须建在网格线上而两个格子行相邻或列相邻意味着它们共享一条网格线边界。桥梁长度的计算如果两个格子的行差≤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。对于一对建筑可能存在多对格子满足条件取所有可能桥梁长度的最小值作为该建筑对的最短桥梁长度。优化目标需要找到一个边集使得优先最小化不连通分量的数量即尽可能多的建筑被连接。在不连通分量数量最小的前提下最小化使用的桥梁数量。在桥梁数量相同的前提下最小化桥梁总长度。这等价于在由建筑为顶点、可行桥梁为边的图中找出一个最小生成森林按桥梁长度排序的Kruskal\texttt{Kruskal}Kruskal算法因为Kruskal\texttt{Kruskal}Kruskal在无负权边的情况下会优先选择最短的边自然地使每个连通分量内的总长度最小同时使用的边数也是该分量最小生成树的边数即顶点数减111。特殊情况如果整个城市只有一个建筑不需要桥梁。如果没有任何可行的桥梁输出No bridges are possible.并输出不连通组数即建筑数量。如果桥梁数量为111输出时使用单数形式bridge。解题思路步骤一标记建筑连通块使用888方向DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS遍历网格为每个#格子分配建筑编号。同时记录每个建筑包含的所有格子坐标以及建筑的行列范围用于后续可能的剪枝但本题直接枚举所有格子对即可。步骤二枚举所有可行的桥梁对于每对不同的建筑iii和jjj枚举它们的所有格子对(p,q)(p, q)(p,q)其中ppp属于建筑iiiqqq属于建筑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 22这种情况在之前已单独处理。否则输出桥梁数量和总长度如果存在多个连通组还要输出组数。复杂度分析建筑数量最多为r×c≤104r \times c \le 10^4r×c≤104但实际建筑数量通常远小于此。枚举所有建筑对并枚举格子对最坏情况下每个建筑只有一个格子即所有#都不相邻格子对的数量为O(K2)O(K^2)O(K2)其中KKK为#的数量。KKK最大为10410^4104K2108K^2 10^8K2108在时限内勉强可行实际数据不会达到最坏情况。并查集操作近似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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN105;constintMAXB10005;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;vectorpairint,intcells;}bld[MAXB];voidfloodFill(intx,inty,intid){if(x0||xr||y0||yc)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].minRowmin(bld[id].minRow,x);bld[id].maxRowmax(bld[id].maxRow,x);bld[id].minColmin(bld[id].minCol,y);bld[id].maxColmax(bld[id].maxCol,y);for(intd0;d8;d)floodFill(xdx[d],ydy[d],id);}structBridge{intu,v,len;booloperator(constBridgeother)const{returnlenother.len;}};vectorBridgebridges;intparent[MAXB];intfindSet(intx){if(parent[x]!x)parent[x]findSet(parent[x]);returnparent[x];}boolunionSet(intx,inty){intrxfindSet(x),ryfindSet(y);if(rxry)returnfalse;parent[rx]ry;returntrue;}voidsolve(intcityNum){memset(comp,-1,sizeof(comp));compCount0;for(inti0;iMAXB;i){bld[i].minRowbld[i].minCol1e9;bld[i].maxRowbld[i].maxCol-1e9;bld[i].cells.clear();}for(inti0;ir;i)for(intj0;jc;j)if(grid[i][j]#comp[i][j]-1)floodFill(i,j,compCount);if(compCount2){printf(City %d\nNo bridges are needed.\n,cityNum);return;}bridges.clear();for(inti0;icompCount;i){for(intji1;jcompCount;j){intminLen1e9;for(autocellA:bld[i].cells){for(autocellB:bld[j].cells){intdrabs(cellA.first-cellB.first);intdcabs(cellA.second-cellB.second);if(dr1)minLenmin(minLen,dc-1);if(dc1)minLenmin(minLen,dr-1);}}if(minLen1e9)bridges.push_back({i,j,minLen});}}sort(bridges.begin(),bridges.end());for(inti0;icompCount;i)parent[i]i;inttotalLen0,used0;for(autob:bridges)if(unionSet(b.u,b.v)){totalLenb.len;used;}intgroups0;for(inti0;icompCount;i)if(findSet(i)i)groups;if(used0){printf(City %d\nNo bridges are possible.\n,cityNum);if(groups1)printf(%d disconnected groups\n,groups);}else{printf(City %d\n,cityNum);if(used1)printf(1 bridge of total length %d\n,totalLen);elseprintf(%d bridges of total length %d\n,used,totalLen);if(groups1)printf(%d disconnected groups\n,groups);}}intmain(){intcityNum0;while(scanf(%d %d,r,c)2){if(r0c0)break;for(inti0;ir;i)scanf(%s,grid[i]);if(cityNum0)printf(\n);solve(cityNum);}return0;}总结本题综合考察了以下几个关键知识点连通块标记使用888方向DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS将角部接触的方格合并为同一建筑这是处理网格连通性问题的基础技巧。几何建模将建筑抽象为顶点可行桥梁抽象为带权边将原问题转化为图论中的最小生成森林问题。这里的关键在于正确计算桥梁长度需要考虑建筑的边界桥梁长度等于两个建筑相邻边之间的网格线距离而不是简单的曼哈顿距离。多目标优化优先最小化不连通分量数通过最小生成森林自动实现其次最小化桥梁数量边数最后最小化总长度Kruskal\texttt{Kruskal}Kruskal按长度排序。由于每条桥梁长度均为正数Kruskal\texttt{Kruskal}Kruskal自然地在连通分量数固定的前提下使用了最少的边数即顶点数减111。实现细节注意桥梁数量为111时的单复数形式。每个案例之间输出一个空行但最后一个案例后不能有多余空行。对于没有可行桥梁的情况需要输出不连通组数即建筑数量。通过本题可以加深对图论模型构建、并查集应用以及网格问题处理技巧的理解。