H1N1

題目描述

H1N1來勢洶洶，一個區域内的城鎮要共同抵禦疫情……

這個區域内共有N座城鎮，其中Q個城鎮已經建好了防疫站，為了防疫工作的需要，每個城鎮必須有公路通到至少一個防疫站，現在已有一些修好的路可以利用。修建第i個城鎮到第j個城鎮的公路花費cost(i，j)，還有有P個城鎮由于條件優越，可以花錢建防疫站。這N個城鎮的人民找到了會程式設計的你，至少要花多少錢可以完成防疫？

輸入檔案

第1行： 3個整數 N，Q，P

下來Q行，每行一個整數Ki，表示第K個城鎮已有防疫站，

下來P行，每行2個整數Ti和price_i,表示在第Ti個城鎮修建防疫站的價格為price_i

以下N*N的矩陣，第i行第j列的整數 表示cost（i，j）

最後N*N的矩陣，第i行第j列的整數 第i個城鎮與第j個城鎮之間的道路有無情況，為0或者1，1表示已經修建好的，0表示還沒有道路。

題目保證2個矩陣都是對稱的（a[i,j] = a[j,i]）且主對角線都為0（a[i,i]=0 , i=1..n）。

輸出檔案

1行 1個整數ans，表示最少的花費。

樣例輸入

3 1 1

1

3 1

0 3 3

3 0 5

3 5 0

0 1 0

1 0 0

0 0 0

樣例輸出

1

注釋

【樣例解釋】

城鎮1已建好防疫站，且1-2有道路已經修好。隻需在城鎮3建防疫站，花費1.

【資料範圍】

對于100%的資料

N<=700

0<=Q,P<=N

Cost,price 均為 1-100000 間的整數，題目保證P+Q>0

對于 20% 的資料 P=0,Q=1

對于 30% 的資料 N<=10

分析

這個題叫做最小生成樹。。。我用的是kruskal。

首先我們需要一個超級大源點0，把它與沒有建站的點連起來，邊權賦為建站的代價price。然後這樣就可以正常跑最小生成樹了。

按題意，本來就有道路的城市間的邊要把邊權指派為0，再加入到邊集數組裡面，并不是先union這兩個點，因為求最小生成樹時并不一定選了這條邊，是以不能先union。否則可能讓ingraph多于n-1條，此時求的就并不是最小生成樹了。邊權若為負，那麼就要WA了

代碼

type
 rec=record
   s,t,v:longint;
   end;
var ingraph,price,m,ans,n,q,p,x,i,j:longint;
    cost:array[..]of rec;
    father:array[..]of longint;
    map:array[..,..]of longint;
function find(x:longint):longint;
begin
  if father[x]=x then exit(x);
  father[x]:=find(father[x]);
  exit(father[x]);
end;

procedure union(a,b:longint);
begin
  father[find(a)]:=find(father[b]);
end;

procedure qsort(b,e:longint);
var l,r,m:longint;
    t:rec;
begin
  l:=b;r:=e;m:=cost[(l+r)shr ].v;
  while l<r do
    begin
      while cost[l].v<m do inc(l);
      while m<cost[r].v do dec(r);
      if l<=r then
        begin
          t:=cost[l];
          cost[l]:=cost[r];
          cost[r]:=t;
          inc(l);
          dec(r);
        end;
    end;
  if l<e then qsort(l,e);
  if b<r then qsort(b,r);
end;

begin
  assign(input,'h1n1.in');
  assign(output,'h1n1.out');
  reset(input);
  rewrite(output);
  readln(n,q,p);
  m:=;
  for i:= to q do
    begin
      read(x);
      inc(m);
      cost[m].s:=;
      cost[m].t:=x;
      cost[m].v:=;
    end;
  for i:= to p do
    begin
      read(x);
      read(price);
      inc(m);
      cost[m].s:=;
      cost[m].t:=x;
      cost[m].v:=price;
    end;
  for i:= to n do
    for j:= to n do read(map[i,j]);

  for i:= to n do father[i]:=i;

  for i:= to n do
    for j:= to n do
      begin
        read(x);
        if (i>j) then
        begin
          if x=
            then
              begin
                inc(m);
                cost[m].s:=i;
                cost[m].t:=j;
                cost[m].v:=;
              end
            else
              begin
                inc(m);
                cost[m].s:=i;
                cost[m].t:=j;
                cost[m].v:=map[i,j];
              end;
        end;
      end;
  qsort(,m);
  ans:=;   ingraph:=;  i:=;
  while (ingraph<n+)do  
    begin
      inc(i);
      if find(cost[i].s)<>find(cost[i].t) then
        begin
          inc(ingraph);
          inc(ans,cost[i].v);
          union(cost[i].s,cost[i].t);
        end;
    end;
  write(ans);
  close(input);
  close(output);
end.