今天是吴耀轩老师的讲解~

今天的主要内容:图论

如何学好图论?

学好图论的基础:必须意识到图论!

邻接矩阵存图:

其缺点是显而易见的:1. 空间复杂度O(n^2)不能接受;2.有重边的时候很麻烦;

优点很简单啦:好写qwq(是不是有点糊弄)

邻接表

一些vector的细节:

生成树

既然它是一颗树,那么应该满足无环!

比如这样它就是一颗有环树!

看个题:

实际上就是让你求最小瓶颈树!qwq

显然红色的更优!

这些是做这个题的做法:

并查集

Kruskal

判断是否构成环:并查集判断是否在一颗树上!

贴上Kruskal的代码:

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;
struct edge {
int u, v, w;
}edg[maxn];
int n, m, p[maxn], ans = ; bool cmp(edge a, edge b)
{return a.w < b.w;}
int findp(int t)
{return p[t] ? p[t] = findp(p[t]) : t;}
bool merge(int u, int v)
{
u = findp(u); v = findp(v);
if (u == v) return false;
p[u] = v; return true;
}
int main()
{
cin >> n >> m;
for (int i = , u, v, w; i <= m; i++)
cin >> u >> v >> w, edg[i] = (edge){u, v, w};
sort(edg + , edg + m + , cmp); for (int i = ; i <= m; i++)
if (merge(edg[i].u, edg[i].v))
ans = max(ans, edg[i]. w);
cout << ans << endl;
}

最新文章

  1. 全局响应MotionEvent
  2. Codeforces 209 C. Trails and Glades
  3. div在Iframe 被遮挡解决方法
  4. js小效果-双色球
  5. 天朝专用- 配置pypi镜像
  6. Oracle 数据库优化-分析现有的sql
  7. UVa784 Maze Exploration
  8. php改写session到数据库
  9. 黑马程序员_Java面向对象_包
  10. 2016-12-30 PHP JS
  11. 用自定义注解实现fastjson序列化的扩展
  12. SQL CTE递归
  13. netty 对象序列化传输示例
  14. ﺑﯘﻟﺒﯘﻟﻼﺭ--思恋--IPA--维吾尔语
  15. MT【44】抛物线不常见性质3
  16. JavaScript基础一
  17. collectionView代理方法快速设置cell大小上下左右间隔
  18. Amazon ec2 改成密码登录方式
  19. 用CSS3把列表项目反转显示
  20. Java多线程(六) —— 线程并发库之并发容器

热门文章

  1. 计算机网络(TCP/IP)
  2. docker 入门4 - 群 【翻译】
  3. Python实现字符的冒泡排序——说实话,两个数兑换的方法震惊了我,一天比一天感受到了Python的强大
  4. Vim 添加vimgdb支持
  5. C#之Action和Func
  6. HTML的标签简单概括
  7. mysql启动失败“MySQL Daemon failed to start”
  8. VM安装vmtools后centos7无法上网
  9. Maven基本概念——根目录、项目创建、坐标
  10. Delphi 数组特性