鱼C论坛

 找回密码
 立即注册
查看: 1770|回复: 1

[技术交流] 次小生成树

[复制链接]
发表于 2018-12-12 16:27:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
最小生成树有kruskal算法,那么我们如何求出次小生成树呢?先跑一边最小生成树,然后依次选择一条最小生成树中的边并删除,在新的图里跑最小生成树。将所有删除一条边的图全部跑完最小生成树后,选取最小的那个长度和就是次小生成树的路径长度和。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-12-12 16:31:27 | 显示全部楼层

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int N=102;
  7. const int INF=1<<30;
  8. struct edge
  9. {
  10.   int fr,to,w,nxt;
  11.   //int samee;
  12.   bool deleted,inmst;
  13.     bool operator < (const edge &a) const {
  14.         return w<a.w;
  15.     }
  16. };
  17. int pre[N],n,m,head[N],cnt,tmp=0;
  18. edge e[N*(N-1)+5];
  19. void add(int fr,int to,int w)
  20. {
  21.     e[cnt].fr=fr;
  22.     e[cnt].to=to;
  23.     e[cnt].w=w;
  24.     e[cnt].nxt=head[fr];
  25.     e[cnt].deleted = false;
  26.     e[cnt].inmst=false;
  27.     head[fr]=cnt++;
  28.    
  29. }
  30. int fin(int x)
  31. {
  32.     if(x==pre[x])
  33.         return x;
  34.     return pre[x]=fin(pre[x]);
  35. }
  36. int Kruskal1()
  37. {
  38.   
  39.     for(int i=1;i<=n;++i)
  40.         pre[i]=i;
  41.     sort(e,e+2*m);
  42.     int ans=0;
  43.    
  44.     for(int i=0;i<cnt;++i)
  45.       {
  46.         //if (e[i].deleted == true){continue;}
  47.         int u=fin(e[i].fr);
  48.         int v=fin(e[i].to);
  49.        
  50.         if(u!=v)
  51.           {
  52.             
  53.             ans+=e[i].w;
  54.             e[i].inmst=true;
  55.             //tmp++;
  56.             pre[u]=v;
  57.         }
  58.     }
  59.     return ans;
  60. }

  61. int Kruskal2()
  62. {
  63.   
  64.     for(int i=1;i<=n;++i)
  65.         pre[i]=i;
  66.     sort(e,e+cnt);
  67.     int ans=0;
  68.    
  69.     for(int i=0;i<cnt;++i)
  70.       {
  71.         if (e[i].deleted == true){/*cout << 1 <<  endl;*/continue;}
  72.         int u=fin(e[i].fr);
  73.         int v=fin(e[i].to);
  74.         //        cout << e[i].deleted << endl;
  75.         if(u!=v)
  76.           {
  77.             
  78.             ans+=e[i].w;
  79.             //e[i].inmst=true;
  80.             
  81.             pre[u]=v;
  82.           }
  83.       }
  84.     return ans;
  85. }

  86. int main()
  87. {
  88.   int a,b,c;
  89.   int T;
  90.   cin >> T;
  91.   while (T--)
  92.     {
  93.       cin >> n >> m;
  94.       //while(scanf("%d",&n)&&n)
  95.       //{
  96.       cnt=0;
  97.       //int m=n*(n-1)/2;
  98.       memset(head,-1,sizeof(head));
  99.       for (int i=0;i<m;i++)
  100.         {
  101.           scanf("%d%d%d",&a,&b,&c);
  102.           add(a,b,c);
  103.           add(b,a,c);
  104.           /* int gg;
  105.           // gg=e[cnt
  106.           e[cnt-1].samee=cnt-2;
  107.           e[cnt-2].samee=cnt-1;
  108.           printf("%d %d\n",e[cnt-1].samee,e[cnt-2].samee);*/
  109.         }

  110.   
  111.       printf("%d ",Kruskal1());
  112.       //cout << cnt << endl;
  113.       int smst = 999999999;
  114.       for (int i=0;i<cnt;i++)
  115.         {
  116.           if (e[i].inmst==true)
  117.             {
  118.               e[i].deleted = true;
  119.               e[i+1].deleted=true;
  120.               //cout << smst << endl;
  121.               smst=min(smst,Kruskal2());
  122.               e[i].deleted= false;
  123.               e[i+1].deleted = false;
  124.             }
  125.         }
  126.       printf("%d\n",smst);
  127.     }
  128.   return 0;
  129. }
复制代码

这个代码可能有问题,但是思路是对的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 15:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表