Agri-Net.(POJ-1258)(最小生成树)
最小生成树算法。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<vector> using namespace std; const int INF = 1000000000; int cost[105][105]; int mincost[105]; bool used[105]; int n,a; int prim() { for(int i=0;i<n;i++) { mincost[i] = INF; used[i] = false; } mincost[0] = 0; int res = 0; while(true) { int v = -1; for(int u=0;u<n;u++) { if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v = u; } if(v==-1) break; used[v] = true; res+=mincost[v]; for(int u=0;u<n;u++) { mincost[u] = min(mincost[u],cost[v][u]); } } return res; } int main() { while(~scanf("%d",&n)) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) { scanf("%d",&cost[i][j]); } printf("%d\n",prim()); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。