题意：
求图中的最小生成树和次小生成树。
题解：
一种容易想到的方法是枚举删除最小生成树上的边，再求最小生成树。用kruskal这种算法的复杂度为O(n*elog2e)，当图比较稠密时，复杂度接近O(n^3)。
但有一种更简单的方法：先求最小生成树T，枚举添加不在T中的边，则添加后一定会形成环。找到环上边值第二大的边(即环中属于T中的最大边)，把它删掉，计算当前生成树的权值，取所有枚举修改的生成树的最小值，即为次小生成树。
这种方法在实现时有更简单的方法：首先求最小生成树T，然后从每个结点u遍历最小生成树T，用一个二维数组max[u][v]记录结点u到结点v的路劲上边的最大值(即最大边的值)。然后枚举不在T中的边(u,v)，计算T- max[u][v] + w(u,v)的最小值，即为次小生成树的权值。显然，这种方法的时间复杂度为O(n^2 + e)。
可见，第二种算法将原来的时间复杂度O(n^3)提高到了O(n^2)。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int maxn=105,INF=0x3f3f3f3f; int n,m; int pre[maxn],mincost[maxn]; bool vis[maxn],used[maxn][maxn]; int cost[maxn][maxn],path[maxn][maxn]; void init() { memset(pre,-1,sizeof(pre)); memset(path,0,sizeof(path)); memset(vis,false,sizeof(vis)); memset(used,false,sizeof(used)); for(int i=1;i<=n;i++) mincost[i]=INF; } int prim() { init(); int res=0; mincost[1]=0; while(1) { int v=-1; for(int u=1;u<=n;u++) if(!vis[u]&&(v==-1||mincost[u]<mincost[v])) v=u; if(v==-1) break; if(pre[v]!=-1) { used[pre[v]][v]=used[v][pre[v]]=true; for(int u=1;u<=n;u++) { if(vis[u]) path[u][v]=path[v][u]=max(path[u][pre[v]],cost[v][pre[v]]); } } vis[v]=true; res+=mincost[v]; for(int u=1;u<=n;u++) { if(mincost[u]>cost[u][v]) { mincost[u]=cost[u][v]; pre[u]=v; } } } return res; } int sec_mst(int res) { int ans=INF; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(!used[i][j]) ans=min(ans,res-path[i][j]+cost[i][j]); } return ans; } int main() { int t; cin>>t; while(t--) { cin>>n>>m; init(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cost[i][j]=INF; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; cost[a][b]=cost[b][a]=c; } int ans=prim(); printf("%d %d ",ans,sec_mst(ans)); } return 0; }