bzoj1601 / P1550 [USACO08OCT]打井Watering Hole（堆优化prim）

P1550 [USACO08OCT]打井Watering Hole

 

对于自己建水库的情况，新建一个虚拟结点，和其他点的边权即为自建水库的费用

这样问题就转化为一个裸最小生成树问题了。

这里用堆优化prim解决。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cctype>

 #include<queue>

 #define re register

 using namespace std;

 void read(int &x){

     char c=getchar();x=;

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

 }

 struct data{

     int d,u;

     data(){}

     data(int A,int B):

         d(A),u(B)

     {}

     bool operator < (const data &tmp) const{return d>tmp.d;}

 };priority_queue <data> h;

 #define N 305

 int n,a[N][N],d[N],ans; bool vis[N];

 int main(){

     read(n);++n; int k=;

     for(re int i=;i<n;++i)

         read(a[n][i]),a[i][n]=a[n][i];//新建边

     for(re int i=;i<n;++i)

         for(re int j=;j<n;++j)

             read(a[i][j]);

     memset(d,,sizeof(d));

     h.push(data(d[]=,));

     while(!h.empty()&&k<n){

         data x=h.top(); h.pop();

         if(vis[x.u]) continue;

         vis[x.u]=; ++k; ans+=x.d;

         for(re int i=;i<=n;++i)

             if(a[x.u][i]){

                 if(d[i]>a[x.u][i]){

                     d[i]=a[x.u][i];

                     h.push(data(a[x.u][i],i));

                 }

             }

     }printf("%d",ans);

     return ;

 }