我的思路是把已有的边赋成0,然后Prim.
程序:
var
  m:array[1..300,1..300] of longint;
  n,t,ans:longint;
procedure init;
var
  i,j,a,b:longint;
begin
  readln(n);
  for i:=1 to n do
    begin
      for j:=1 to n do read(m[i,j]);
      readln;
    end;
  readln(t);
  for i:=1 to n do
    for j:=1 to n do
      if m[i,j]=0 then m[i,j]:=maxlongint;
  for i:=1 to t do
    begin
      readln(a,b);
      m[a,b]:=0;
    end;
  ans:=0;
end;
procedure prim;
var
  l,c:array[1..300] of longint;
  mark:array[1..300] of boolean;
  i,j,k,min:longint;
begin
  for i:=1 to n do
    begin
      l[i]:=m[1,i];
      c[i]:=1;
    end;
  l[1]:=-1;
  for i:=1 to n-1 do
    begin
      min:=maxlongint;
      for j:=1 to n do
        if (l[j]<min)and(l[j]<>-1) then
          begin
            min:=l[j];
            k:=j;
          end;
      ans:=ans+m[c[k],k];
      l[k]:=-1;
      for j:=1 to n do
        if m[k,j]<l[j] then
          begin
            l[j]:=m[k,j];
            c[j]:=k;
          end;
    end;
end;
procedure print;
begin
  writeln(ans);
end;
begin
  while not seekeof do
    begin
      init;
      prim;
      print;
    end;
end.

• 感觉是不是这样的就成有向了？ (1330) TN 2005-06-11 21:39:07
  • 按题目意思似乎是有向 (0) JiangLY 2005-06-11 21:39:43
    • 实际上不是 (0) frkstyc 2005-06-11 21:40:00
      • 21:40:00.0 (0) frkstyc 2005-06-11 21:40:18
        • 强~ (0) JiangLY 2005-06-11 21:41:58
          • 你快了2秒 (0) frkstyc 2005-06-11 21:42:28
        • 似乎最后一位从来都是0..... (0) TN 2005-06-11 21:42:19
          • 最后四位就不是拉 (0) frkstyc 2005-06-11 21:42:54
      • 那就是无向了? (0) JiangLY 2005-06-11 21:42:18
        • 嗯 (0) TN 2005-06-11 21:42:24
          • ft...AC (0) JiangLY 2005-06-11 21:43:41
            • rpwt (0) frkstyc 2005-06-11 21:44:00
            • hiahia,我的第一没被抢走 (0) TN 2005-06-11 21:44:37