1002 搭桥
有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。
在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。
在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。
样例1
3 5
#...#
..#..
#...#
样例2
3 5
##...
.....
....#
样例3
3 5
#.###
#.#.#
###.#
样例4:
3 5
#.#..
.....
....#
样例1
5
4 4
样例2
2
0 0
样例3
1
0 0
样例4
3
1 1
见描述
这题我真心没觉得有多模板题，一些细节也很坑，至少我是嗑了很久，说是模板题的大爷们我先献上膝盖:)。
这道题挺神奇的，比如我这种辣鸡第一眼就没看出是最小生成树，最后乱搞碰壁才发现可以写prim…
坑点挺多的，而且题目本身也很迷。
思路：无向图。第一问就是求联通块个数，可以用搜索水过，但是要注意“如果某两个单元格有一个点相联系，则它们属于同一座建筑物”，意思就是要搜索每个单元格的八个方向。后两问是建立在第一问上的。把相邻的建筑合成一个建筑来提高效率。我这里使用了并查集。在第一问的搜索中加入把相邻的建筑父亲都指向编号，比如第一组相邻的建筑合成的一个建筑编号为1，第二组编号为2…这就是把这些建筑缩为点，点的编号就是建筑组的编号。接下来考虑如何建边。建边也是这道题目的难点之一。我们可以发现对于每一个建筑，如果它上面那一行或者下面那一行有建筑的话，它们之间桥梁的距离就可以用横坐标相减再减1计算出来，而对于同一行的也是如此。对于每一列的也可以这样枚举。这里我用的是邻接矩阵存储图，注意存两个点之间的距离时要用min，因为你不知道这条边会不会比它已经存好的边短。建完图后我们就来跑Prim。有很多建筑组，而且这些建筑组之间不一定有边联通。以每个dis值还没确定的点为源点跑Prim，最后计算答案就可以了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=;
long long ans2,ans3;
int n,m,f[],num[][],e[][],ans1,dis[];
int D[][]={{,},{,},{,-},{-,},{-,-},{,},{,-},{-,}};
bool map[][],map2[][],book[];
int read()
{
int x=,f=; char c=getchar();
while (c<'' || c>'') {if (c=='-') f=-; c=getchar();}
while (c>=''&& c<='') {x=x*+c-''; c=getchar();}
return (x*f);
}
int getf(int x)
{
if (f[x]==x) return x;
f[x]=getf(f[x]);
return f[x];
}
bool Merge(int a,int b)
{
a=getf(a); b=getf(b);
if (a!=b) {
return ;
}
return ;
}
void dfs(int x,int y)
{
num[x][y]=ans1;
map2[x][y]=;
for (int i=; i<=; i++) {
int xx=x+D[i][],yy=y+D[i][];
if (xx>=&&xx<=n&&yy>=&&yy<=m&&map2[xx][yy]==) {
f[num[xx][yy]]=f[num[x][y]];
dfs(xx,yy);
}
}
return;
}
int main()
{
char c;
n=read(); m=read();
for (int i=; i<=n; i++)
for (int j=; j<=m; j++) {
cin>>c;
if (c=='#') {
map[i][j]=;
map2[i][j]=;
}
}
for (int i=; i<=n; i++)
for (int j=; j<=m; j++)
if (map2[i][j]==) {
ans1++;
f[ans1]=ans1;
dfs(i,j);
}
if (ans1==) {
cout<<<<endl<<<<" "<<<<endl;
return ;
}
for (int i=; i<=ans1; i++)
for (int j=; j<=ans1; j++)
e[i][j]=inf;
for (int i=; i<=n; i++) {
for (int j=; j<=m; j++) {
if (map[i][j]==) {
if (i!=) {
for (int k=; k<=m; k++)
if (map[i-][k]== && Merge(num[i-][k],num[i][j])) {
e[num[i-][k]][num[i][j]]=min(e[num[i-][k]][num[i][j]],abs(k-j)-);
e[num[i][j]][num[i-][k]]=e[num[i-][k]][num[i][j]];
}
}
if (i!=n) {
for (int k=; k<=m; k++)
if (map[i+][k]== && Merge(num[i+][k],num[i][j])) {
e[num[i+][k]][num[i][j]]=min(abs(k-j)-,e[num[i+][k]][num[i][j]]);
e[num[i][j]][num[i+][k]]=e[num[i+][k]][num[i][j]];
}
}
for (int k=; k<=m; k++)
if (map[i][k]== && Merge(num[i][k],num[i][j])) {
e[num[i][k]][num[i][j]]=min(abs(k-j)-,e[num[i][k]][num[i][j]]);
e[num[i][j]][num[i][k]]=e[num[i][k]][num[i][j]];
}
if (j!=) {
for (int k=; k<=n; k++)
if (map[k][j-]== && Merge(num[k][j-],num[i][j])) {
e[num[k][j-]][num[i][j]]=min(abs(k-i)-,e[num[k][j-]][num[i][j]]);
e[num[i][j]][num[k][j-]]=e[num[k][j-]][num[i][j]];
}
}
if (j!=m) {
for (int k=; k<=n; k++)
if (map[k][j+]== && Merge(num[k][j+],num[i][j])) {
e[num[k][j+]][num[i][j]]=min(abs(k-i)-,e[num[k][j+]][num[i][j]]);
e[num[i][j]][num[k][j+]]=e[num[k][j+]][num[i][j]];
}
}
for (int k=; k<=n; k++){
if (map[k][j]== && Merge(num[k][j],num[i][j])) { e[num[k][j]][num[i][j]]=min(abs(k-i)-,e[num[k][j]][num[i][j]]);
e[num[i][j]][num[k][j]]=e[num[k][j]][num[i][j]];
}
}
}
}
}
for (int i=; i<=ans1; i++) {
if (book[i]==) {
for (int j=; j<=ans1; j++) dis[j]=inf;
dis[i]=;
for (int k=; k<ans1; k++) {
int MIN=inf,u;
for (int j=; j<=ans1; j++)
if (book[j]==&&dis[j]<MIN) {
MIN=dis[j];
u=j;
}
if (MIN==inf) break;
book[u]=;
for (int j=; j<=ans1; j++)
if (book[j]==&&e[u][j]<dis[j]) dis[j]=e[u][j];
}
for (int j=; j<=ans1; j++)
if (dis[j]!=inf && dis[j]!=) {
ans2++;
ans3+=dis[j];
}
}
}
printf("%d\n%lld %lld\n",ans1,ans2,ans3);
return ;
}
搭桥
有问题可以直接在评论里面提问，有需要转载的请得到我的允许，否则按侵权处理。
Elena loves NiroBC forever!