/* 次小生成树 kruskal
*/
#include <iostream> #include <algorithm> using namespace std; int n,m,parent[600]; bool flag[260000]; struct node { int x,y,w; }tree[260000]; int cmp(node aa,node bb) { return aa.w<bb.w; } void makeset() { int x; for(x=1;x<=n;x++) parent[x]=x; } int findset(int x) { if(x!=parent[x]) parent[x]=findset(parent[x]); return parent[x]; } void unionset(int x,int y) { x=findset(x); y=findset(y); if(parent[x]==parent[y]) return ; parent[y]=x; } int kruskal() { int i,j,cnt=0,res=0; sort(tree,tree+m,cmp); makeset(); for(i=0;i<m;i++) { if(findset(tree[i].x)!=findset(tree[i].y)) { cnt++; unionset(tree[i].x,tree[i].y); flag[i]=1; res+=tree[i].w; } if(cnt==n-1) break; } if(cnt==n-1) return res; else return -1; } int sec_kruskal() { int i,j,cnt=0,res=0,minc=99999999,fg=0,flg=0; for(i=0;i<m;i++) { if(flag[i]) { makeset(); flg=0; cnt=0; res=0; for(j=0;j<m;j++) { if(j!=i && findset(tree[j].x)!=findset(tree[j].y)) { cnt++; unionset(tree[j].x,tree[j].y); res+=tree[j].w; } if(cnt==n-1) { fg=1; flg=1; break; } } if(minc>res && flg) minc=res; } } if(fg) return minc; else return -1; } int main() { int i,j,minc=999999999; scanf("%d%d",&n,&m); for(i=0;i<m;i++) scanf("%d%d%d",&tree[i].x,&tree[i].y,&tree[i].w); printf("Cost: %d/n",kruskal()); printf("Cost: %d/n",sec_kruskal()); return 0; }
