传送门：poj1258 Agri-Net
最小生成树模板题，借着这道题再重新整理下最小生成树。
算法：Prim 和 Kruskal
1.Prim：从任一节点出发，不断扩展
- 使用数据结构：堆
- 时间复杂度：O(ElogV)或O(VlogV+E)(斐波那契堆)
- 适用于密集图
- 若不用堆，则时间复杂度为O(V^2)
2.Kruskal:将所有边从小到大加入，在此过程中判断是否构成回路
- 使用数据结构：并查集
- 时间复杂度：O(ElogE)
- 适用于稀疏图
代码1：Prim+堆优化
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
struct Edge{int v; //边端点，另一端点已知 int w; //边权值 Edge(int v_=0,int w_=INF):v(v_),w(w_){}bool operator <(const Edge &e)const{return w>e.w; //在队列里，边权值越小越优先 }
};vector<vector<Edge> >G(110);
int HeapPrim(const vector<vector<Edge> >&G,int n){ //G是邻接表，n是顶点数目，返回值是最小生成树权值和 Edge tmp(0,0);priority_queue<Edge> pq; //存放顶点以及该顶点到在建生成树的距离 vector<int> dist(n);vector<int> vis(n); //标记是否已经被加入最小生成树 int cnt=0; //已经被加入最小生成树的顶点数目 for(int i=0;i<n;i++){dist[i]=INF;vis[i]=0;}int ans=0; //最小生成树总权值 pq.push(Edge(0,0)); //开始只有顶点是0，它到最小生成树距离是0 while(cnt<n&&!pq.empty()){do{ //每次从队列里拿在建生成树最近的点 tmp=pq.top();pq.pop();}while(vis[tmp.v]==1&&!pq.empty());if(vis[tmp.v]==0){ans+=tmp.w;vis[tmp.v]=1;cnt++;for(int i=0;i<G[tmp.v].size();i++){ //更新新加入点的邻点 int k=G[tmp.v][i].v;if(vis[k]==0){int w=G[tmp.v][i].w;if(dist[k]>w){dist[k]=w;pq.push(Edge(k,w));}}}}}if(cnt<n) return -1; //图不连通 return ans; /*时间复杂度分析：考察了所有的边，且考察一条边时，可能执行pq.push(Edge(k,w)) 故复杂度为O(E*logV) */}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;G[i].push_back(Edge(j,w));}cout<<HeapPrim(G,n)<<endl;}
}代码2：Kruskal
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
struct Edge{int s,e,w; //起点，终点，权值 Edge(int s_,int e_,int w_):s(s_),e(e_),w(w_){}Edge(){}bool operator <(const Edge &e)const{return w<e.w; }
};vector<Edge> E;
vector<int> par;int fi(int x){if(par[x]!=x) return par[x]=fi(par[x]);return x;
}void join(int x,int y){int fx=fi(x),fy=fi(y);if(fx!=fy) par[fy]=fx;
}int main(){int n;while(cin>>n){E.clear();par.clear();for(int i=0;i<n;i++) par.push_back(i);for(int i=0;i<n;i++)for(int j=0;j<n;j++){int w;cin>>w;E.push_back(Edge(i,j,w));}sort(E.begin(),E.end());int cnt=0,ans=0;for(int i=0;i<E.size();i++){if(fi(E[i].s)!=fi(E[i].e)){join(E[i].s,E[i].e);cnt++;ans+=E[i].w;}if(cnt==n-1) break;}cout<<ans<<endl;}
}