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

见描述

dfs可以解决第一问；

第二问用最小生成树做

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 string s;
  7 
  8 int dx[9]={0,0,0,1,-1,1,1,-1,-1},dy[9]={0,1,-1,0,0,1,-1,1,-1};
  9 
 10 int book[55][55],pos[55][55];
 11 const int N=2505;
 12 int father[N*2];
 13 
 14 struct node{
 15     int u,v,w;
 16     bool operator < (const node &a)const     
 17     {
 18          return w<a.w;
 19      }
 20 }e[N*100];
 21 int map[55][55];
 22 
 23 int n,m;
 24 int ans=0,cnt=0;
 25 
 26 
 27 void dfs(int x,int y)
 28 {
 29     book[x][y]=ans;
 30     for(int i=0;i<=8;i++)
 31     {
 32         if(map[x+dx[i]][y+dy[i]])
 33         {
 34             map[x+dx[i]][y+dy[i]]=0;
 35             dfs(x+dx[i],y+dy[i]);
 36         }
 37     }
 38     return ;
 39     
 40 }
 41 
 42 bool unionn(int x1,int y1,int x2,int y2,int w)
 43 {
 44     if(y2<1||y2>m||x2<1||x2>n||!book[x2][y2]) return 1;
 45     if(book[x1][y1]==book[x2][y2]) return 0;
 46     cnt++;
 47     e[cnt].u=book[x1][y1];
 48     e[cnt].v=book[x2][y2];
 49     e[cnt].w=w-1;
 50     return 1;
 51 }
 52 
 53 void build(int x ,int y)
 54 {
 55     for(int i=x+1; i<=n; i++)
 56         if(!unionn(x,y,i,y,i-x)||!unionn(x,y,i,y+1,i-x)||!unionn(x,y,i,y-1,i-x))
 57             break;
 58     for(int i=x-1; i>0; i--)
 59         if(!unionn(x,y,i,y,x-i)||!unionn(x,y,i,y+1,x-i)||!unionn(x,y,i,y-1,x-i))
 60             break;
 61     for(int i=y+1; i<=m; i++)
 62         if(!unionn(x,y,x,i,i-y)||!unionn(x,y,x-1,i,i-y)||!unionn(x,y,x+1,i,i-y))
 63             break;
 64     for(int i=y-1; i>0; i--)
 65         if(!unionn(x,y,x,i,y-i)||!unionn(x,y,x-1,i,y-i)||!unionn(x,y,x-1,i,y-i))
 66             break;
 67 }
 68 
 69 void work()
 70 {
 71     for(int i=1;i<=n;i++)
 72     for(int j=1;j<=m;j++)
 73     {
 74         if(pos[i][j])build(i,j);
 75     }
 76     return ;
 77 }
 78 
 79 int find(int x)
 80 {
 81     if(father[x]!=x)father[x]=find(father[x]);
 82     return father[x];
 83 }
 84 
 85 int main()
 86 {
 87     scanf("%d%d",&n,&m);
 88     for(int i=1;i<=n*m;i++)father[i]=i;
 89     for(int i=1;i<=n;i++)
 90     {
 91         cin>>s;
 92         for(int j=0;j<s.size();j++)
 93         {
 94             if(s[j]=='#')pos[i][j+1]=map[i][j+1]=1;
 95             else map[i][j+1]=0;
 96             //if(map[i][j+1]==1&&map[i-1][j+1]==0&&map[i][j]==0)cnt++;
 97         }
 98             
 99     }
100     //printf("%d",cnt);
101     for(int i=1;i<=n;i++)
102     for(int j=1;j<=m;j++)
103     {
104         if(map[i][j]==1)
105         {
106             map[i][j]=0;
107             dfs(i,j);
108             ans++;
109         }
110     }
111     printf("%d
",ans);
112     int sum=0;
113     for(int i=1;i<=ans;i++)father[i]=i;
114     work();
115     sort(e+1,e+cnt+1);
116     ans=0;
117     for(int i=1;i<=cnt;i++) 
118     {
119         int p=find(e[i].u),q=find(e[i].v);
120         if(p!=q) 
121         {
122             father[p]=q;
123             ans++;
124             sum+=e[i].w;
125         }
126     }
127     printf("%d %d",ans,sum);
128     
129     return 0;
130 
131 }