次小生成树

bobpanda

最小生成树有kruskal算法，那么我们如何求出次小生成树呢?先跑一边最小生成树，然后依次选择一条最小生成树中的边并删除，在新的图里跑最小生成树。将所有删除一条边的图全部跑完最小生成树后，选取最小的那个长度和就是次小生成树的路径长度和。

bobpanda

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=102;
const int INF=1<<30;
struct edge
{
  int fr,to,w,nxt;
  //int samee;
  bool deleted,inmst;
    bool operator < (const edge &a) const {
        return w<a.w;
    }
};
int pre[N],n,m,head[N],cnt,tmp=0;
edge e[N*(N-1)+5];
void add(int fr,int to,int w)
{
    e[cnt].fr=fr;
    e[cnt].to=to;
    e[cnt].w=w;
    e[cnt].nxt=head[fr];
    e[cnt].deleted = false;
    e[cnt].inmst=false;
    head[fr]=cnt++;
    
}
int fin(int x)
{
    if(x==pre[x])
        return x;
    return pre[x]=fin(pre[x]);
}
int Kruskal1()
{
  
    for(int i=1;i<=n;++i)
        pre[i]=i;
    sort(e,e+2*m);
    int ans=0;
    
    for(int i=0;i<cnt;++i)
      {
        //if (e[i].deleted == true){continue;}
        int u=fin(e[i].fr);
        int v=fin(e[i].to);
        
        if(u!=v)
          {
            
            ans+=e[i].w;
            e[i].inmst=true;
            //tmp++;
            pre[u]=v;
        }
    }
    return ans;
}

int Kruskal2()
{
  
    for(int i=1;i<=n;++i)
        pre[i]=i;
    sort(e,e+cnt);
    int ans=0;
    
    for(int i=0;i<cnt;++i)
      {
        if (e[i].deleted == true){/*cout << 1 <<  endl;*/continue;}
        int u=fin(e[i].fr);
        int v=fin(e[i].to);
        //        cout << e[i].deleted << endl;
        if(u!=v)
          {
            
            ans+=e[i].w;
            //e[i].inmst=true;
            
            pre[u]=v;
          }
      }
    return ans;
}

int main()
{
  int a,b,c;
  int T;
  cin >> T;
  while (T--)
    {
      cin >> n >> m;
      //while(scanf("%d",&n)&&n)
      //{
      cnt=0;
      //int m=n*(n-1)/2;
      memset(head,-1,sizeof(head));
      for (int i=0;i<m;i++)
        {
          scanf("%d%d%d",&a,&b,&c);
          add(a,b,c);
          add(b,a,c);
          /* int gg;
          // gg=e[cnt
          e[cnt-1].samee=cnt-2;
          e[cnt-2].samee=cnt-1;
          printf("%d %d\n",e[cnt-1].samee,e[cnt-2].samee);*/
        }
 
  
      printf("%d ",Kruskal1());
      //cout << cnt << endl;
      int smst = 999999999;
      for (int i=0;i<cnt;i++)
        {
          if (e[i].inmst==true)
            {
              e[i].deleted = true;
              e[i+1].deleted=true;
              //cout << smst << endl;
              smst=min(smst,Kruskal2());
              e[i].deleted= false;
              e[i+1].deleted = false;
            }
        }
      printf("%d\n",smst);
    }
  return 0;
}

这个代码可能有问题，但是思路是对的。