洛谷P1546 最短网络 Agri-Net(Prim堆优化)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5005;
 4 const int INF=0x3f3f3f3f;
 5 inline void read(int &tmp)
 6 {
 7     int x=1;char c=getchar();
 8     for(tmp=0;!isdigit(c);c=getchar()) if(c=='-') x=-1;
 9     for(;isdigit(c);tmp=tmp*10+c-48,c=getchar());
10     tmp*=x;
11 }
12 int n,sum,tot,m,mp[maxn][maxn],w[maxn];
13 typedef pair<int,int> P;
14 priority_queue< P,vector<P>,greater<P> >q;
15 bool v[maxn];
16 void Prim()
17 {
18     memset(w,0x3f,sizeof(w));
19     w[1]=0;q.push(make_pair(0,1));
20     while(!q.empty())
21     {
22         int Top=q.top().second;q.pop();
23         if(v[Top]) continue;
24         v[Top]=1;sum+=w[Top];++tot;
25         for(int i=1;i<=n;i++)
26             if(mp[Top][i]<w[i]&&mp[Top][i]>0&&v[i]==false) {w[i]=mp[Top][i];q.push(make_pair(w[i],i));}
27     }
28 } 
29 int main()
30 {
31     read(n);
32     for(int i=1;i<=n;i++)
33         for(int j=1;j<=n;j++)
34                 {read(mp[i][j]);if(i==j) mp[i][j]=INF;}
35     Prim();
36     printf("%d",sum);
37     return 0;
38 }