例题:https://vjudge.net/problem/POJ-1679
算法描述:关于次小生成树,首先求出最小生成树,然后枚举每条不在最小生成树上的边(在原本的节点上添加一个vis属性进行判断即可),并把这条边放到最小生成树上面,然后就一定会形成环,那么我们在这条环路中取出一条(除了新加入的那一条边)最长的路。利用二维数组d[][]来维护环路中最长的路径。最后依次遍历每条未加入最小生成树的边,即可求出次小生成树。
关于这个算法有些地方还没想明白,特别是合并路径那一块的代码的具体含义我不太清楚,先放个板子在这吧!
:)
已更新完毕,大致弄明白了,这个p[N]存在的意义主要是实现对d[N][N]的实时更新,第49行的功能也就显而易见了,p[N]要保存所有点和其相关点的关系,说到底,其实就是一个邻接表的实现。
—————————————————————————————————
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int N=2e2+5,M=1e5+5; struct rec{ int x,y,z; bool vis; }edge[M]; int fa[N],d[N][N]; vector<int> p[N];//拓展路径,其实是寻找关联节点 int n,m,t,k; bool operator<(rec a,rec b){ return a.z<b.z; } int get(int x){ if(x==fa[x]) return x; return fa[x]=get(fa[x]); } int main(){ scanf("%d",&t); while(t--){ k=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ p[i].clear(); p[i].push_back(i); fa[i]=i; } for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); edge[++k].x=x,edge[k].y=y,edge[k].z=z,edge[k].vis=false; } sort(edge+1,edge+1+k); int ans=0; for(int i=1;i<=k;i++){ int x=get(edge[i].x),y=get(edge[i].y); if(x==y) continue; ans+=edge[i].z; fa[x]=y; edge[i].vis=true; int l1=p[x].size(),l2=p[y].size(); for(int j=0;j<l1;j++) for(int k=0;k<l2;k++) d[p[x][j]][p[y][k]]=d[p[y][k]][p[x][j]]=edge[i].z; //由kru算法的特性,遍历到的边只会愈来愈大,故能只需等于当前数值即可更新两点间的最大边权 for(int j=0;j<l1;j++) p[y].push_back(p[x][j]); //合并路径,由于fa[x]=y,寻找与x相关的y是可以直接找到的,故只要添加与y关联的x即可 } int ans_2=0x3f3f3f3f; for(int i=1;i<=k;i++) if(!edge[i].vis) ans_2=min(ans_2,ans+edge[i].z-d[edge[i].x][edge[i].y]); if(ans_2>ans) printf("%d\n",ans); else printf("Not Unique!\n"); } return 0; }