| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
第二次敲Prim#include <iostream> #include <queue> #include <vector> #include <cstring> using namespace std; typedef long long ll; const int maxn=102; struct edge{ int to; ll cost; edge(int x,ll y):to(x),cost(y){} edge(){} bool operator< (const edge& xx) const{ return xx.cost<cost; } }; priority_queue<edge> que; ll G[maxn][maxn]; //邻接矩阵; int n; bool vis[maxn]; ll prim() { ll res=0; vis[1]=1; for(int i=2;i<=n;i++) //该点相邻的点均入队列; que.push(edge(i,G[1][i])); while(!que.empty()) { edge e=que.top(); que.pop(); if(vis[e.to])continue; res+=e.cost; vis[e.to]=1; for(int i=1;i<=n;i++)//新加入的点的相邻边入队列; if(i!=e.to) que.push(edge(i,G[e.to][i])); } return res; } int main() { while(cin >> n) { memset(vis,0,sizeof(vis)); while(!que.empty()) que.pop(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin >> G[i][j]; ll ans=prim(); cout << ans << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator