pascal程序题 连接格点

问题描述:

pascal程序题 连接格点
连接格点 程序名:grid.pas/c/cpp 输入文件:grid.in 输出文件:grid.out 时限:1秒 有一个M行N列的点阵,相邻两点可以相连.一条纵向的连线花费一个单位,一条横向的连线花费两个单位.某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通.输入数据 第一行输入两个正整数m和n.以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线.输入保证|x1-x2|+|y1-y2|=1.输出数据 输出使得连通所有点还需要的最小花费.输入样例 2 2 1 1 2 1 输出样例 3 数据规模 m,n
1个回答 分类:综合 2014-09-23

问题解答:

我来补答
这题是:最小生成树(kruscal) 程序如下: var i,j,n,m,t1,t2,ans,x1,y1,x2,y2,x,y:longint; b:array[0..1000000] of longint; function dj(t:longint):longint; begin if tb[t] then b[t]:=dj(b[t]); dj:=b[t]; end; begin assign(input,'grid.in');reset(input); assign(output,'grid.out');rewrite(output); readln(m,n); for i:=1 to m*n do b[i]:=i; ans:=0; while not eof do begin readln(x1,y1,x2,y2); x:=dj((x1-1)*n+y1); y:=dj((x2-1)*n+y2); b[x]:=y; end; for i:=1 to n do for j:=1 to m-1 do begin x:=dj((j-1)*n+i); y:=dj(j*n+i); if xy then begin ans:=ans+1; b[x]:=y; end; end; for i:=1 to m do for j:=1 to n-1 do begin x:=dj((i-1)*n+j); y:=dj((i-1)*n+j+1); if xy then begin ans:=ans+2; b[x]:=y; end; end; writeln(ans); close(input); close(output); end.
 
 
展开全文阅读
剩余:2000
下一页:请说清为什么