开启辅助访问 切换到宽版

奇迹创客社区

 注册
 登录
搜索
热搜: NOIP OIer 神牛
信息学基地社区»论坛 › 青少年信息学 › 信息学奥赛 › OJ题解 › 1406: 最短网络
返回列表 发新帖
查看: 394|回复: 1

1406: 最短网络

[复制链接]
Hank

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
发表于 2021-6-14 10:45:44 | 显示全部楼层 |阅读模式
11111111111111
回复

使用道具 举报

Hank

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
 楼主| 发表于 2021-6-14 11:00:35 | 显示全部楼层
本帖最后由 Hank 于 2021-6-14 11:17 编辑

First:MST
首先呢，我们一看这题：
图+最短+铺线=MST
(至于MST是吗，BDBS)
所以模板一上，一打，诶，完了！
Second:code
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<string>
  6. #include<cmath>
  7. #include<algorithm>
  8. #include<iomanip>
  9. using namespace std;

  11. #define MAX 1000

  13. int forest[MAX], n, tot;

  15. struct Edge
  16. {
  17.         int from;
  18.         int to;
  19.         int w;
  20. }edges[MAX * MAX];

  22. int find(int x)
  23. {
  24.         if(forest[x] != x)
  25.         {
  26.                 return forest[x] = find(forest[x]);
  27.         }
  28.         else
  29.         {
  30.                 return x;
  31.         }

  33. }

  35. void join(int a, int b)
  36. {
  37.         forest[find(a)] = find(b);
  38. }

  40. bool cmp(Edge a, Edge b)
  41. {
  42.         return a.w < b.w;
  43. }

  45. int main()
  46. {
  47.         cin >> n;
  48.         
  49.         int r = 0;
  50.         
  51.         for(int i = 0;i < n;++i)
  52.         {
  53.                 forest[i] = i;
  54.         }
  55.         
  56.         for(int i = 0;i < n;++i)
  57.         {
  58.                 for(int j = 0;j < n;++j)
  59.                 {
  60.                         int v;
  61.                         
  62.                         cin >> v;
  63.                         
  64.                         if(v)
  65.                         {
  66.                                 r++;
  67.                                 
  68.                                 edges[r].from = i + 1;
  69.                                 edges[r].to = j + 1;
  70.                                 edges[r].w = v;
  71.                         }
  72.                 }
  73.         }
  74.         
  75.         sort(edges, edges + r, cmp);
  76.         
  77.         int e = 0;
  78.         
  79.         for(int i = 0;i < r;++i)
  80.         {
  81.                 if(find(edges[i].from) != find(edges[i].to))
  82.                 {
  83.                         join(edges[i].from, edges[i].to);
  84.                         tot += edges[i].w;
  85.                         e++;
  86.                 }
  87.                
  88.                 if(e == n - 1)
  89.                 {
  90.                         break;
  91.                 }
  92.         }
  93.         
  94.         cout << tot;
  95.         
  96.         return 0;
  97.         
  98. }
复制代码



Third:彩蛋
歌曲必听，你必须听一听，而且每次听都不一样，Trust me!
code时听有奇效


回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

津ICP备19006949号-1 | 津公网安备12010102000465号

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