风灵无畏OI

【题目描述】

连接格点

问题描述

    有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

输入数据

    第一行输入两个正整数m和n。

    以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。

输出数据

    输出使得连通所有点还需要的最小花费。

输入样例

2 2

1 1 2 1

输出样例

3

时间限制   各测试点1秒

内存限制   你的程序将被分配32MB的运行空间

数据规模 m,n<=1000

【题目大意】

        有一个 M 行 N 列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花 费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

【题目分析】

1.  既然要连通，那么自然想到最小生成树,可是边的数量会很多,而kruskal算法是要用 （ElogE）的时间排序的。肯定超时。

2.  进一步思考，边的权值无非只有3种，已经连好的为0，纵向边为1，横向边为2，那么只要按0,1,2的顺序来存就可以得到有序的边集数组了，然后就是传统的kruskal。

【程序代码】

type  rec=record

         x,y:longint;

       end;

var p:array[1..1000,1..1000]of rec;

      m,n:longint;

function equal(a,b:rec):boolean;

begin

   exit((a.x=b.x) and (a.y=b.y))

end;//判断是否相等，相当于kruskal中判断是否在同一集合中的操作

function findset(x,y:longint):rec;

begin

   if (p[x,y].x<>x) or (p[x,y].y<>y) then

      p[x,y]:=findset(p[x,y].x,p[x,y].y);

   exit(p[x,y]);

end;//相当于kruskal中找爸爸的操作

procedure readp;

var

   x1,y1,x2,y2,i,j:longint;

   t:rec;

begin

   readln(m,n);

   for i:=1 to m do

   for j:=1 to n do

   begin

      t.x:=i;

      t.y:=j;

      p[i,j]:=t;

   end;//初始父亲为自己

   repeat

      readln(x1,y1,x2,y2);

      p[findset(x1,y1).x,findset(x1,y1).y]:=findset(x2,y2);

   until eof;//把本身就已经连了的点放到一个集合中

end;

procedure solve;

var i,j,ans:longint;

begin

   ans:=0;

   for j:=1 to n do

   for i:=1 to m-1 do

      if not equal(findset(i,j),findset(i+1,j)) then

      begin

         p[p[i,j].x,p[i,j].y]:=p[i+1,j];

         inc(ans);

      end;//解决边权为1的边

   for i:=1 to m do

   for j:=1 to n-1 do

      if not equal(findset(i,j),findset(i,j+1)) then

      begin

         p[p[i,j].x,p[i,j].y]:=p[i,j+1];

         inc(ans,2);

      end;//解决边权为2的边

   writeln(ans);

end;

begin

   assign(input,'grid.in');    reset(input);

   assign(output,'grid.out'); rewrite(output);

   readp;

   solve;

   close(input); close(output);

end.