【数据结构】 最小生成树（四）——利用kruskal算法搞定例题×3+

　　这道题怎么办？似乎找不到和最小生成树的关系，和图似乎有点关系，可是怎么写呢？这又是一个迷，先看代码再解释：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,a[1000][1000],ans[1000],cnt,w[1000],minn;bool vis[1000]={false};
 5 int main()
 6 {
 7     scanf("%d",&n);
 8     for(int i=1;i<=n;i++)
 9     for(int j=1;;j++)
10     {
11         scanf("%d",&a[i][j]);
12         if(a[i][j]==0) break;w[i]++;
13     }
14     for(int i=1;i<=n;i++)
15     {
16         minn=999999,k=0;
17         for(int j=1;j<=n;j++)
18         {
19             if(vis[j]==true) continue;
20             if(w[j]<minn)
21             {
22                 k=j;
23                 minn=w[j];
24             }
25         }
26         vis[k]=true;ans[++cnt]=k;
27         for(int j=1;j<=n;j++)
28         {
29             if(vis[j]==true) continue;
30             for(int l=1;l<=n;l++)
31             if(a[j][l]==k) w[j]--;
32         }
33     }
34     for(int i=cnt;i>=1;i--)
35     printf("%d ",ans[i]);
36     return 0;
37 }

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

　　对，你没有看错，它虽然身处最小生成树中，但是却不需要高级数据结构，说白了就是个找规律题，小编也是瞎猫碰见死耗子，随便一脑洞大开就AC了，当然，也欢迎用最小生成树写出的大佬评论感受，下面来讲一讲小编找出的规律：首先，题目告诉要把父辈排在子辈前面，小编想到了用并查集，但是貌似写不出来，于是小编就猜想是不是儿子越多，辈分就越高，那么如果儿子一样多又该怎么处理呢？接着，小编想了各种方法处理，最后突然想到可以让他们减少儿子，那又怎么减呢？把已经定位好辈分的人从剩下人的儿子中抹掉，假装其他人都失去了这个儿子。那么是应该先挑小辈呢？还是先挑长辈呢？当然是先挑小辈，因为比较好选，优先选长辈会出现很多奇怪的状况，小编亲手试过，有了这个大思路，小编就以试试的心态写出了这个代码，没想到竟然过了，这道题不需要用树，不需要图，不需要最小生成树竟然可以过，纯找规律，真是道大水题。

　　原本小编还是一知半解的，写了几道题以后终于弄明白了，建议大家也可以写一写。

附测评网站：

　　1.【例4-9】城市公交网建设问题

　　2.【例4-10】最优布线问题

　　3.【例4-11】最短网络(agrinet)

　　4.【例4-12】家谱树

　　5.局域网(net)

（编辑：厦门网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!