【POJ 2485】 Highways
最小生成树模板
Prim
;int mp[501][501];int dis[501];bool vis[501];int n;int Prim(){int i,j,w,p,mm = 0;memset(dis,-1,sizeof(dis));memset(vis,0,sizeof(vis));dis[1] = 0;for(i = 0; i < n; ++i){w = INF;for(j = 1; j <= n; ++j){if(!vis[j] && dis[j] < w && dis[j] != -1){p = j;w = dis[j];}}vis[p] = 1;mm = max(mm,w);for(j = 1; j <= n; ++j){if(!vis[j] && (dis[j] == -1 || dis[j] > mp[p][j]))dis[j] = mp[p][j];}}return mm;}int main(){int t,i,j;scanf(“%d”,&t);while(t–){scanf(“%d”,&n);for(i = 1; i <= n; ++i){for(j = 1; j <= n; ++j){scanf(“%d”,&mp[i][j]);}}printf(“%d\n”,Prim());}return 0;}
Kruskal
;typedef struct Edge{int u,v,w;Edge a)const{return w < a.w;}}Edge;Edge eg[255555];int pre[555];int tp;void Init(int n){int i;for(i = 1; i <= n; ++i)pre[i] = i;}int Find(int x){if(x != pre[x]) pre[x] = Find(pre[x]);return pre[x];}int main(){int t,n,i,j,w,k,r,mm,cnt;scanf(“%d”,&t);while(t–){tp = 0;scanf(“%d”,&n);Init(n);for(i = 1; i <= n; ++i){for(j = 1; j <= n; ++j){scanf(“%d”,&w);if(j > i){eg[tp].w = w;eg[tp].u = i;eg[tp++].v = j;}}}sort(eg,eg+tp);mm = cnt = 0;for(i = 0; i < tp; ++i){k = Find(eg[i].u);r = Find(eg[i].v);if(k != r){pre[k] = r;mm = max(mm,eg[i].w);cnt++;}if(cnt == n-1) break;}printf(“%d\n”,mm);}return 0;}
，看着它或是汹涌或是平静，然而一直相随，不离不弃。
