【POJ 2485】 Highways

最小生成樹模板

Prim

#includeusing namespace std;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

#includeusing namespace std;typedef struct Edge {int u,v,w;bool operator < (const struct 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; }

總結(jié)

以上是生活随笔為你收集整理的【POJ 2485】 Highways的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。