Agri-Net最短网络

【问题描述】

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000

【输入格式】(agrinet.in)

第一行：农场的个数，N（3<=N<=100）。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。

【输出格式】(agrinet.out)

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

【样例输入】

0 4 9 21

4 0 8 17

9 8 0 16

21 17 16 0

【样例输出】

【思路分析】

对于求过每一个节点的最小距离：

将此题转化为求无向图的最小生成树，可以用prime或者克鲁斯卡尔算法来求最小生成树！…………

var dist:array[1..1000,1..1000] of longint;
    n,i,j,k,q,x,y,total:longint;
    a,b,w,f:array[1..100000] of longint;
function get(x:longint):longint;
begin
  if f[x]=x then exit(x);
    f[x]:=get(f[x]);
  exit(f[x]);
end;
procedure kuaipai(st,ed:longint);
var i,j,mid,mm:longint;
begin
 if st>=ed then exit;
 i:=st-1; j:=ed+1;
 mid:=w[(st+ed) div 2];
 while i<J do
  begin
   repeat inc(i) until w[i]>=mid;
   repeat dec(j) until w[j]<=mid;
   if i<j then
    begin
     mm:=a[i];a[i]:=a[j];a[j]:=mm;
     mm:=b[i];b[i]:=b[j];b[j]:=mm;
     mm:=w[i];w[i]:=w[j];w[j]:=mm;
    end;
  end;
 kuaipai(st,j);kuaipai(j+1,ed);
end;
begin
  assign(input,'agrinet.in');reset(input);
  assign(output,'agrinet.out');rewrite(output);
  readln(n);
  for i:=1 to n do f[i]:=i;
   for i:=1 to n do
    for j:=1 to n do
     begin
      read(dist[i,j]);
      if i<j then
        begin
         inc(q);
         a[q]:=i;
         b[q]:=j;
         w[q]:=dist[i,j];
        end;
      end;
   kuaipai(1,q);
   total:=0;
  for i:=1 to q do
   begin
    x:=get(a[i]);
    y:=get(b[i]);
    if x<>y then
     begin
      f[x]:=y;
      inc(total,w[i]);
    end;
   end;
  writeln(total);
 close(input);close(output);
end.

文章来源地址https://uudwc.com/A/dbyVN