42 lines
1.0 KiB
Markdown
42 lines
1.0 KiB
Markdown
- 链星
|
|
```c
|
|
inline void add_edge(int u, int v, int w) {
|
|
edge[cnt].next = head[u]; edge[cnt].v = v; edge[cnt].w = w; head[u] = cnt++;
|
|
}
|
|
```
|
|
- Dijkstra最短路
|
|
- 要求：边权非负（不仅仅是没有负环）
|
|
- 随手敲一个
|
|
```c
|
|
priority_queue<node, vector<node>, greater<node>> pq;
|
|
pq.push({s, 0});
|
|
dis[s] = 0;
|
|
while(!pq.empty()) {
|
|
int u = pq.top().id;
|
|
pq.pop();
|
|
if (vis[u]) continue;
|
|
vis[u] = true;
|
|
for (int i = head[u]; i; i = edge[i].next) {
|
|
int v = edge[i].to;
|
|
if (dis[v] > dis[u] + edge[i].w) {
|
|
dis[v] = dis[u] + edge[i].w;
|
|
pq.push({v, dis[v]});
|
|
}
|
|
}
|
|
}
|
|
```
|
|
- Kruscal生成树
|
|
- ```c++
|
|
std::sort(e + 1, e + e_cnt + 1);
|
|
int ans = 0, t_cnt = 0;
|
|
for (int i = 1; i <= n; ++ i) fa[i] = i;
|
|
for (int i = 1; i <= e_cnt; ++ i) {
|
|
int fau = findfa(e[i].u);
|
|
int fav = findfa(e[i].v);
|
|
if (fau != fav) {
|
|
fa[fav] = fau; // attention! use fa[find(v)], not fa[v]
|
|
ans += e[i].w;
|
|
t_cnt ++;
|
|
}
|
|
}
|
|
``` |