有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市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

题解

3000+B的码农题,这题一年前就开始在打了,可是当时一直调不过,就拖到了今天,我还是太弱了QwQ...

对于第一问,就是bfs求八个方向的连通块,bfs的同时再新建一个二维数组b,b[i][j]表示第[i][j]个位置的块属于哪一个连通块.

然后就是建图,这一步是最麻烦的.

枚举n*m个点,每个点再枚举9个方向:上右、上、上左、左上、左、左下、下左、下、下右、右下、右、右上.

如果遇到b[i][j]不同就建边,遇到b[i][j]相同则两点用并查集合在一起.

将图建出来之后就跑一遍最小生成树Kruskal{其实Prim也可以}.

将所有边按权值大小从小到大排,然后从最小的边开始枚举,如果两点已经在同一个集合的话就直接跳过,如果两点还没有在同一集合,就将两点所在的集合合并,并增加边数的答案以及权值之和的答案.

3892B Code:

const fx:array[1..8] of -1..1=(0,1,0,-1,-1,1,1,-1);const fy:array[1..8] of -1..1=(1,0,-1,0,-1,1,-1,1);var f:array[1..100000,1..2] of longint;var c:array[1..1000,1..1000] of char;var b:array[1..1000,1..1000] of longint;var cost,x,y,fa:array[1..100000] of longint;var i,j,n,m,ans1,ans2,ans3,k,t,tt,cnt:longint;procedure qs(l,r:longint);//quicksortvar i,j,t,m:longint;begin  i:=l;j:=r;m:=cost[(l+r) div 2];  repeat    while cost[i]<m do inc(i);    while cost[j]>m do dec(j);    if i<=j then    begin      t:=cost[i];cost[i]:=cost[j];cost[j]:=t;      t:=x[i];x[i]:=x[j];x[j]:=t;      t:=y[i];y[i]:=y[j];y[j]:=t;      inc(i);dec(j);    end;  until i>j;  if i<r then qs(i,r);if l<j then qs(l,j);end;procedure bfs(x,y,k:longint);//求连通块var i,j,front,nx,ny,p,rear:longint;begin  inc(ans1);  front:=0;rear:=1;  f[rear,1]:=x;f[rear,2]:=y;  c[x,y]:=‘Z‘;b[x,y]:=k;//标记b数组  while front<rear do  begin    inc(front);    for i:=1 to 8 do    begin      nx:=f[front,1]+fx[i];      ny:=f[front,2]+fy[i];      if (nx>0)and(nx<=n)and(ny>0)and(ny<=m)and(c[nx,ny]=‘#‘) then      begin        inc(rear);        f[rear,1]:=nx;f[rear,2]:=ny;        b[nx,ny]:=k;c[nx,ny]:=‘Z‘;      end;    end;  end;end;function v(x,y:longint):longint; begin exit((x-1)*m+y); end;procedure build(x1,y1,x2,y2:longint);begin  inc(cnt);  x[cnt]:=v(x1,y1);  y[cnt]:=v(x2,y2);  if abs(x1-x2)<=1 then cost[cnt]:=abs(y1-y2)-1 else  if abs(y1-y2)<=1 then cost[cnt]:=abs(x1-x2)-1;end;function gf(x:longint):longint;begin  if fa[x]=x then gf:=x else  fa[x]:=gf(fa[x]);gf:=fa[x];end;procedure merge(x,y:longint); begin x:=gf(x);y:=gf(y);fa[x]:=y; end;begin  readln(n,m);  for i:=1 to n do  begin    for j:=1 to m do read(c[i,j]);    readln;  end;  for i:=1 to n*m do fa[i]:=i;//初始化并查集数组  for i:=1 to n do for j:=1 to m do if c[i,j]=‘#‘ then begin inc(k);bfs(i,j,k); end;  for i:=1 to n do//建图  for j:=1 to m do  begin    tt:=b[i,j];if tt=0 then continue;    for k:=i+1 to n do    begin      if b[k,j]=tt then merge(v(i,j),v(k,j));      if b[k,j-1]=tt then merge(v(i,j),v(k,j-1));      if b[k,j+1]=tt then merge(v(i,j),v(k,j+1));      if (b[k,j]<>tt)and(b[k,j]<>0) then build(i,j,k,j);      if j-1>0 then if (b[k,j-1]<>tt)and(b[k,j-1]<>0) then build(i,j,k,j-1);      if j+1<=m then if (b[k,j+1]<>tt)and(b[k,j+1]<>0) then build(i,j,k,j+1);    end;    for k:=i-1 downto 1 do    begin      if b[k,j]=tt then merge(v(i,j),v(k,j));      if b[k,j-1]=tt then merge(v(i,j),v(k,j-1));      if b[k,j+1]=tt then merge(v(i,j),v(k,j+1));      if (b[k,j]<>tt)and(b[k,j]<>0) then build(i,j,k,j);      if j-1>0 then if (b[k,j-1]<>tt)and(b[k,j-1]<>0) then build(i,j,k,j-1);      if j+1<=m then if (b[k,j+1]<>tt)and(b[k,j+1]<>0) then build(i,j,k,j+1);    end;    for k:=j+1 to m do    begin      if b[i,k]=tt then merge(v(i,j),v(i,k));      if b[i-1,k]=tt then merge(v(i,j),v(i-1,k));      if b[i+1,k]=tt then merge(v(i,j),v(i+1,k));      if (b[i,k]<>tt)and(b[i,k]<>0) then build(i,j,i,k);      if i-1>0 then if (b[i-1,k]<>tt)and(b[i-1,k]<>0) then build(i,j,i-1,k);      if i+1<=n then if (b[i+1,k]<>tt)and(b[i+1,k]<>0) then build(i,j,i+1,k);    end;    for k:=j-1 downto 1 do    begin      if (b[i,k]<>tt)and(b[i,k]<>0) then build(i,j,i,k) else if b[i,k]=tt then merge(v(i,j),v(i,k));      if i-1>0 then if (b[i-1,k]<>tt)and(b[i-1,k]<>0) then build(i,j,i-1,k) else if b[i-1,k]=tt then merge(v(i,j),v(i-1,k));      if i+1<=n then if (b[i+1,k]<>tt)and(b[i+1,k]<>0) then build(i,j,i+1,k) else if b[i+1,k]=tt then merge(v(i,j),v(i+1,k));    end;  end;  qs(1,cnt);  for i:=1 to cnt do//Kruskal  begin    if gf(x[i])=gf(y[i]) then continue else    begin      merge(x[i],y[i]);      inc(ans3,cost[i]);      inc(ans2);    end;  end;  writeln(ans1);  writeln(ans2,‘ ‘,ans3);end.


测试点#brig0.in 结果:AC 内存使用量: 1260kB 时间使用量: 14ms 
测试点#brig1.in 结果:AC 内存使用量: 368kB 时间使用量: 2ms 
测试点#brig2.in 结果:AC 内存使用量: 492kB 时间使用量: 1ms 
测试点#brig3.in 结果:AC 内存使用量: 240kB 时间使用量: 1ms 
测试点#brig4.in 结果:AC 内存使用量: 496kB 时间使用量: 2ms 
测试点#brig5.in 结果:AC 内存使用量: 364kB 时间使用量: 1ms 
测试点#brig6.in 结果:AC 内存使用量: 364kB 时间使用量: 2ms 
测试点#brig7.in 结果:AC 内存使用量: 496kB 时间使用量: 1ms 
测试点#brig8.in 结果:AC 内存使用量: 752kB 时间使用量: 6ms 
测试点#brig9.in 结果:AC 内存使用量: 1008kB 时间使用量: 11ms 


欢迎转载,若转载请注明出处.