搭桥（codevs 1002）

题目描述 Description

有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。

输入描述 Input Description

在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r 行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。

输出描述 Output Description

在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。

样例输入 Sample Input

样例1

3 5

#...#

..#..

#...#

样例2

3 5

##...

.....

....#

样例3

3 5

#.###

#.#.#

###.#

样例4:

3 5

#.#..

.....

....#

样例输出 Sample Output

样例1

4 4

样例2

0 0

样例3

0 0

样例4

1 1

数据范围及提示 Data Size & Hint

见描述

分析：首先第一问很好求，深搜就可以了，然后第二问，它要求将各个建筑物连起来，并且是每两个建筑物间有一个桥，那么我们就容易想到是一棵树，而且是最小生成树，那么就预先处理一下图中节点间的路径，做克鲁斯卡尔最小生成树就可以了。
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define M 2510
using namespace std;
struct node
{
    int x,y,z;
};node a[M],e[M*M/2];
int fa[M],s,r,n,m;
bool vis[60][60];
char map[60][60];
int ax[8]={0,0,1,-1,1,1,-1,-1};
int ay[8]={1,-1,0,0,1,-1,1,-1};
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
bool cmp(const node&s1,const node&s2)
{
    return s1.z<s2.z;
}
void dfs(int x,int y)
{
    vis[x][y]=true;
    for(int i=0;i<8;i++)
    {
        int xx=x+ax[i],yy=y+ay[i];
        if(xx>=1&&xx<=r&&yy>=1&&yy<=s&&map[xx][yy]=='#'&&!vis[xx][yy])
          dfs(xx,yy);
    }
}
void work1()
{
    scanf("%d%d",&r,&s);
    for(int i=1;i<=r;i++)
      for(int j=1;j<=s;j++)
        cin>>map[i][j];
    int tot=0;
    for(int i=1;i<=r;i++)
      for(int j=1;j<=s;j++)
        if(map[i][j]=='#'&&!vis[i][j])
        {
            tot++;
            dfs(i,j);
        }
    printf("%d
",tot);
}
void work2()
{
    for(int i=1;i<=r;i++)
      for(int j=1;j<=s;j++)
      {
          char c=map[i][j];
          if(c=='#')
          {
              a[++n].x=i;
              a[n].y=j;
          }
      }
    for(int i=1;i<=n;i++)
      for(int j=i+1;j<=n;j++)
        if(abs(a[i].x-a[j].x)<=1)
        {
            e[++m].x=i;e[m].y=j;
            e[m].z=abs(a[i].y-a[j].y);
            if(e[m].z)e[m].z--;
        }
        else if(abs(a[i].y-a[j].y)<=1)
        {
            e[++m].x=i;e[m].y=j;
            e[m].z=abs(a[i].x-a[j].x)-1;
        }
    int sum_v=0,sum_n=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int aa=find(e[i].x),bb=find(e[i].y);
        if(aa!=bb)
        {
            fa[aa]=bb;
            sum_v+=e[i].z;
            if(e[i].z)sum_n++;
        }
    }
    printf("%d %d",sum_n,sum_v);
}
int main()
{
    work1();
    work2();
    return 0;
}

View Code