次小生成树

次小生成树基于prim o（v^2），可以通过次小生成树和最小生成树的值是否相等判断最小生成树是否唯一，若不等，则唯一，反之亦然。
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 const int inf=0x3f3f3f3f;
  7 class SecondMinST_Prim{///次小生成树(无向图基于Prim)o(MV^2)
  8     typedef int typec;///边权的类型
  9     static const int MV=128;///点的个数
 10     int n,pre[MV];
 11     bool vis[MV],used[MV][MV];
 12     typec minst,cimin,cost[MV][MV],Max[MV][MV],lowc[MV];
 13     void Prim() {
 14         minst=0;
 15         mt(vis,0);
 16         mt(Max,0);
 17         mt(used,0);
 18         vis[0]=true;
 19         pre[0]=-1;
 20         for(int i=1; i<n; i++) {
 21             lowc[i]=cost[0][i];
 22             pre[i]=0;
 23         }
 24         lowc[0]=0;
 25         for(int i=1; i<n; i++) {
 26             typec sma=inf;
 27             int p=-1;
 28             for(int j=0; j<n; j++)
 29                 if(!vis[j]&&sma>lowc[j]) {
 30                     sma=lowc[j];
 31                     p=j;
 32                 }
 33             if(sma==inf){
 34                 minst=-1;
 35                 return ;
 36             }
 37             minst+=sma;
 38             vis[p]=true;
 39             used[p][pre[p]]=used[pre[p]][p]=true;
 40             for(int j=0; j<n; j++) {
 41                 if(vis[j])
 42                     Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]);
 43                 if(!vis[j]&&lowc[j]>cost[p][j]) {
 44                     lowc[j]=cost[p][j];
 45                     pre[j]=p;
 46                 }
 47             }
 48         }
 49     }
 50     void smst() {
 51         cimin=inf;
 52         for(int i=0; i<n; i++)
 53             for(int j=i+1; j<n; j++)
 54                 if(cost[i][j]!=inf && !used[i][j]) {
 55                     cimin=min(cimin,minst+cost[i][j]-Max[i][j]);
 56                 }
 57         if(cimin==inf) cimin=-1;
 58     }
 59 public:
 60     void init(int tn){///传入点的个数，下标0开始
 61         n=tn;
 62         for(int i=0;i<n;i++){
 63             for(int j=0;j<n;j++){
 64                 cost[i][j]=i==j?0:inf;
 65             }
 66         }
 67     }
 68     void add(int u,int v,typec w){
 69         if(cost[u][v]>w){
 70             cost[u][v]=w;
 71             cost[v][u]=w;
 72         }
 73     }
 74     void solve(){
 75         Prim();
 76         smst();
 77     }
 78     typec getmin(){
 79         return minst;
 80     }
 81     typec getci(){
 82         return cimin;
 83     }
 84 }gx;
 85 int main(){
 86     int t,n,m;
 87     while(~scanf("%d",&t)){
 88         while(t--){
 89             scanf("%d%d",&n,&m);
 90             gx.init(n);
 91             while(m--){
 92                 int u,v,w;
 93                 scanf("%d%d%d",&u,&v,&w);
 94                 gx.add(u-1,v-1,w);
 95             }
 96             gx.solve();
 97             if(gx.getci()==gx.getmin()){
 98                 puts("Not Unique!");
 99             }
100             else{
101                 printf("%d
",gx.getmin());
102             }
103         }
104     }
105     return 0;
106 }
View Code
end