POJ1358 Agri-Net

 1 #include<cstdio>
 2 #include<vector>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn=110;
 7 const int inf=0x3f3f3f3f;
 8 
 9 struct node{
10     int v,dis;
11     node(){}
12     node(int _v,int _dis){
13         v=_v;
14         dis=_dis;
15     }
16     bool operator<(const node &b) const {
17         return dis>b.dis;
18     }
19 };
20 
21 int n,dis[maxn];
22 vector<node> G[maxn];
23 bool vis[maxn];
24 
25 void prim() {
26     int ans=0,num=0;
27     priority_queue<node> pq;
28     for(int i=0;i<n;i++) {
29         vis[i]=false;
30         dis[i]=inf;
31     }
32     pq.push(node(0,0));
33     node f;
34     while(num<n&&!pq.empty()) {
35         do{
36            f=pq.top();
37            pq.pop();
38         }while(vis[f.v]&&!pq.empty());
39         if(!vis[f.v]) {
40             ans+=f.dis;
41             vis[f.v]=true;
42             num++;
43             for(int i=0;i<G[f.v].size();i++) {
44                 int v=G[f.v][i].v;
45                 if(!vis[v]) {
46                     if(dis[v]>G[f.v][i].dis) {
47                         dis[v]=G[f.v][i].dis;
48                         pq.push(node(v,dis[v]));
49                     }
50                 }
51             }
52         }
53     }
54     if(num<n) printf("-1\n");//因为这里记录的是点的个数。不是边
55     else printf("%d\n",ans);
56 }
57 
58 int main() {
59     while(~scanf("%d",&n)) {
60         memset(G,0,sizeof(G));
61         for(int i=0;i<n;i++) {
62             for(int j=0;j<n;j++) {
63                 int x;
64                 scanf("%d",&x);
65                 if(x) G[i].push_back(node(j,x));
66             }
67         }
68         prim();
69     }
70 }