首页 > 代码库 > codevs 1002 搭桥
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
5
4 4
样例2
2
0 0
样例3
1
0 0
样例4
3
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\n",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 }
codevs 1002 搭桥
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。