【算法】MST-Prim

①初步思路就是最小生成树，那么打井操作怎么办呢？

   打井操作可看做是尤一个超级水源引出水，且代价为Wi的操作，所以加一个“超级点”就可以了，接着MST

1 var  2     n,heapsize,now,i,j:integer;  3     temp,mst:longint;  4     v:array[1..301,1..301] of longint;  5     p:array[1..301] of integer;  6     a,place:array[1..301] of integer;  7     d:array[1..301] of longint;  8     done:array[1..301] of boolean;  9 procedure exchange(x,y:integer); 10 var 11     i,j,temp:integer; 12 begin 13     place[a[x]]:=y; 14     place[a[y]]:=x; 15     temp:=a[x];a[x]:=a[y];a[y]:=temp; 16 end; 17  18 procedure min_heapify(i:integer); 19 var 20     l,r,smaller:integer; 21 begin 22     l:=i shl 1; 23     r:=l+1; 24     smaller:=i; 25     if (d[a[l]]
     
      <=heapsize) then smaller:=l; 26     if (d[a[r]]
      
       <=heapsize) then smaller:=r; 27     if smaller<>i then 28     begin 29         exchange(smaller,i); 30         min_heapify(smaller); 31     end; 32 end; 33  34 procedure change(k:integer;x:longint); 35 var 36     i:integer; 37 begin 38     i:=k; 39     while (i>1)and(d[a[i shr 1]]>x) do 40     begin 41         exchange(i,i shr 1); 42         i:=i shr 1; 43     end; 44 end; 45  46 function extract_min:integer; 47 var 48     i:integer; 49 begin 50     extract_min:=a[1]; 51     a[1]:=a[heapsize]; 52     place[a[1]]:=1; 53     dec(heapsize); 54     min_heapify(1); 55 end; 56  57 procedure build_heap; 58 var 59     i:integer; 60 begin 61     for i:=n div 2 downto 1 do min_heapify(i); 62 end; 63 begin 64    assign(input,'water.in'); 65    reset(input); 66    assign(output,'water.out'); 67    rewrite(output); 68     readln(n); 69    fillchar(done,sizeof(done),false); 70     for i:=1 to n+1 do p[i]:=i; 71     for i:=2 to n+1 do 72     begin 73         readln(temp); 74         v[1,i]:=temp; 75       v[i,1]:=temp; 76     end; 77     for i:=2 to n+1 do 78     begin 79         for j:=2 to n+1 do 80         begin 81             read(temp); 82             v[i,j]:=temp; 83          v[j,i]:=temp; 84         end; 85         readln; 86     end; 87   88     for i:=1 to n+1 do place[i]:=i; 89     for i:=1 to n+1 do a[i]:=i; 90     for i:=1 to n+1 do d[i]:=maxlongint; 91    d[1]:=0; 92     heapsize:=n+1; 93     while heapsize<>0 do 94     begin 95         now:=extract_min; 96         done[now]:=true; 97         for i:=1 to n+1 do if not done[i] then 98         if (d[i]>v[i,now])and(v[i,now]<>0) then 99         begin100             d[i]:=v[i,now];101             change(place[i],v[i,now]);102 103         end;104         MST:=MST+d[now];105    106     end;107     writeln(mst);108    close(input);109    close(output);110 end.