prim方法:先求过一遍prim，同时标记使用过得边。然后同时记录任意2点间的最大值。
每次加入一条新的边，会产生环，删去环中的最大值即可。
#include<stdio.h> #include<string.h> #define INF 99999999 const int maxn = 110; int map[maxn][maxn],vis[maxn],dis[maxn],n,pre[maxn],m,used[maxn][maxn]; int maxd[maxn][maxn]; int max(int x,int y){return x>y?x:y;} int min(int x,int y){return x<y?x:y;} void init() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j)map[i][j]=0; else map[i][j]=INF; } } } int prim() { int ans=0; int i,j,pos; memset(maxd,0,sizeof(maxd)); for(i=1;i<=n;i++) { dis[i]=map[1][i]; vis[i]=0; pre[i]=1; } vis[1]=1; pre[1]=-1; for(i=1;i<n;i++) { int minc=INF; for(j=1;j<=n;j++) { if(!vis[j]&&minc>dis[j]) { pos=j; minc=dis[j]; } } vis[pos]=1; ans+=minc; used[pre[pos]][pos]=used[pos][pre[pos]]=1; for(j=1;j<=n;j++) { if(vis[j]) maxd[pos][j]=maxd[j][pos]=max(maxd[j][pre[pos]],dis[pos]); } for(j=1;j<=n;j++) { if(!vis[j]&&dis[j]>map[pos][j]) { dis[j]=map[pos][j]; pre[j]=pos; } } } return ans; } int dfs(int x) { int ans=INF; int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j)continue; if(map[i][j]!=INF&&!used[i][j]) { ans=min(ans,x+map[i][j]-maxd[i][j]); } } } return ans; } int main() { int i,j,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); for(i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(map[x][y]>z) map[x][y]=map[y][x]=z; } memset(used,0,sizeof(used)); int mst=prim(); int second_mst=dfs(mst); if(second_mst!=mst) printf("%d ",mst); else printf("Not Unique! "); } }