五一培训 清北学堂 DAY5
2024-09-05 06:19:25
今天是吴耀轩老师的讲解~
今天的主要内容:图论
如何学好图论?
学好图论的基础:必须意识到图论!
图
邻接矩阵存图:
其缺点是显而易见的: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;
}
最新文章
- 全局响应MotionEvent
- Codeforces 209 C. Trails and Glades
- div在Iframe 被遮挡解决方法
- js小效果-双色球
- 天朝专用- 配置pypi镜像
- Oracle 数据库优化-分析现有的sql
- UVa784 Maze Exploration
- php改写session到数据库
- 黑马程序员_Java面向对象_包
- 2016-12-30 PHP JS
- 用自定义注解实现fastjson序列化的扩展
- SQL CTE递归
- netty 对象序列化传输示例
- ﺑﯘﻟﺒﯘﻟﻼﺭ--思恋--IPA--维吾尔语
- MT【44】抛物线不常见性质3
- JavaScript基础一
- collectionView代理方法快速设置cell大小上下左右间隔
- Amazon ec2 改成密码登录方式
- 用CSS3把列表项目反转显示
- Java多线程(六) —— 线程并发库之并发容器