XYLX 10.19 H1N1(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

分析

直接加一個超級源點，該源點直接到達即表示建立防疫站。求最小生成樹注意不能加入并查集，否則會出現不是樹的情況。

本人較懶，不想改代碼了。由于權值為0，加入并查集無影響；

代碼如下

program travel;
const mp=;
var i,j,total,n,have,ans,x:longint;
    visited,exist:array[..] of boolean;
    father:array[..] of integer;
    map:array[..,..] of boolean;
    ch:char;
    factorial:array[..] of longint;
procedure dfs(i,step:longint);
var j:longint;
begin
 visited[i]:=true;
 for j:= to n do
  begin
   if map[i,j] and (not visited[j]) then
    begin
     father[j]:=i;
     dfs(j,step+);
     visited[j]:=false;
    end;
  end;
 if (step<>) and (map[i,x])
  then
   begin
    write();
    close(input);
    close(output);
    halt;
   end;
end;

begin
 readln(n);
 fillchar(exist,sizeof(exist),false);
 for i:= to n do
  begin
   for j:= to n do
    begin
     read(ch);
     if ch='Y'
      then
       begin
        map[i,j]:=true;
        exist[i]:=true;
       end
      else map[i,j]:=false;

    end;
   readln;
  end;
 for i:= to n do father[i]:=;
 have:=;
 for x:= to n do
  begin
   if (father[x]=) and (exist[x])
    then
     begin
      inc(total);
      dfs(x,);
     end;
   if not exist[x]
    then
     begin
      inc(have);
     end;
  end;
 ans:=;
 factorial[]:=;
 for i:= to n do
  factorial[i]:=((i mod mp)*(factorial[i-] mod mp)) mod mp;
 for i:= to total do
  begin
   ans:=(ans*) mod mp;
  end;
 ans:=(ans * (factorial[have+total] mod mp)) mod mp;
 write(ans);
end.
           

#