题目地址：http://poj.org/problem?id=1258
裸的算法
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=1<<30;
struct Edge{int vex;int w;Edge(int v=0,int w=INF):vex(v),w(w){}bool operator < (const Edge& e) const {return w>e.w;}
};
//图是邻接表存储 G[u]储存u点出发所有的点
vector<vector<Edge> > G(110); //比Vector<Edge> G[110] 快
int HeapPrim(int n) //返回mst的最小权值
{priority_queue<Edge> PQ;vector<int> dist(n,INF); //所有点到mst的最短距离 vector<bool> used(n,false);int totw=0; //mst 的总权值int DoneNum=0; //收入的点数 PQ.push(Edge(0,0));while(DoneNum<n&&!PQ.empty()){Edge e=PQ.top(); PQ.pop();while(used[e.vex]&&!PQ.empty()) e=PQ.top(),PQ.pop();if(used[e.vex]) continue; //不能 if(PQ.empty())因为第一个点就是empty的 totw+=e.w;used[e.vex]=true;DoneNum++;for(int i=0;i<G[e.vex].size();i++) //该点连接的所有边 {int v=G[e.vex][i].vex;int w=G[e.vex][i].w;if(!used[v]&&dist[v]>w){ //更新到mst的dist值 dist[v]=w;PQ.push(Edge(v,w));}}}if(DoneNum<n) return -1;return totw;
}
int main()
{int n;while(cin>>n){for(int i=0;i<n;i++) G[i].clear();for(int i=0;i<n;i++) //邻接矩阵读取 for(int j=0;j<n;j++){int w;cin>>w;if(i!=j) G[i].push_back(Edge(j,w));}cout<<HeapPrim(n)<<endl;}return 0;
}Kruskal：
Memory: 1060K Time: 110MS
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=10000+5;
int n,m; //n个点 , m条边
struct Edge{int from,to,weight;Edge(int f,int t,int w):from(f),to(t),weight(w){}bool operator < (const Edge& e) const {return weight<e.weight;}
};
vector<Edge> edges;
int p[maxn];
int find(int x) {return p[x]==x?x:p[x]=find(p[x]);
}
int Kruskal()
{int TotW=0;for(int i=0;i<n;i++) p[i]=i;sort(edges.begin(),edges.end());int done=0;for(int i=0;i<m;i++){Edge e=edges[i];int u=e.from, v=e.to, w=e.weight;int up=find(u), vp=find(v);if(up!=vp) TotW+=w,p[up]=vp,done++;if(done==n-1) break; //到n-1条边就结束 } return TotW;
}
int main()
{while(cin>>n){edges.clear();for(int i=0;i<n;i++) //邻接矩阵读取 for(int j=0;j<n;j++){int w;cin>>w;if(i!=j) edges.push_back(Edge(i,j,w));}m=edges.size(); cout<<Kruskal()<<endl;}return 0;
}