\(kruskal\)，一种求最小生成树的算法，其思想与贪心有些相似，具体做法为：、
将边按照边权由小到大排序，每次拿出权值最小的一条边，看它连接的两个顶点是否在同一个连通块中（可以用并查集维护），如果在的话就不使用他，否则就加入生成树，一直加入到边数为\(n - 1\)结束
如何证明？
要我说我也说不明白，还是直接上图吧
图片来自：https://blog.csdn.net/weixin_43272781/article/details/83589394
复杂度：\(O(mlogm)\)
代码实现：
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x <<3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 5011;
const int M = 200011;
struct node {
int x, y, val;
} a[M];
int n, m, k, fa[N], ans = 0;
bool cmp(node a, node b) {
return a.val < b.val;
}
inline int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= m; i++) {
a[i].x = read(), a[i].y = read(), a[i].val = read();
}
stable_sort(a + 1, a + 1 + m, cmp);
for(int i = 1; i <= m; i++) {
int dx = find(a[i].x), dy = find(a[i].y);
if(find(dx) != find(dy)) {
fa[dx] = fa[dy];
ans += a[i].val;
k++;
}
if(k == n - 1) break;
}
cout << ans << '\n';
return 0;
}同样是一种求最小生成树的算法，也用到了贪心的思想，具体做法是：
随便找一个点作为一棵树的根节点，然后找出和它相邻的边（这里邻接表存储，用一遍循环即可），使用一条边扩展这个树，要求这条边一个顶点在树中，另一 个顶点不在树中，并且这条边的权值要求最小。重复以上的步骤，同时维护一个\(dis\)数组，表示为已用点到未用点的最短距离。
证明：\(Prim\)算法之所以是正确的，主要基于一个判断：对于任意一个顶点\(v\)，连接到该顶点的所有边中的一条最短边\((v, v_j)\)必然属于最小生成树（即任意一个属于最小生成树的连通子图，从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树）
复杂度：\(O(elog_2v)\)
来自：https://www.cnblogs.com/bcoier/p/10293059.html
代码实现如下：
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int INF = 1e10 + 11;
const int N = 5011;
const int M = 200011;
struct node {
int to, next, val;
} e[M << 1];
int head[N], dis[N], cnt;
int n, m, k, now = 1, ans = 0;
bool vis[N];
inline void add(int from, int to, int val) {
e[++cnt].to = to;
e[cnt].val = val;
e[cnt].next = head[from];
head[from] = cnt;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int x = read(), y = read(), w = read();
add(x, y, w), add(y, x, w);
}
for(int i = 2; i <= n; i++) dis[i] = INF;
for(int i = head[1]; i; i = e[i].next) dis[e[i].to] = min(dis[e[i].to], e[i].val);
while(++k < n) {
int minn = INF;
vis[now] = 1;
for(int i = 1; i <= n; i++) {
if(!vis[i] && minn > dis[i]) {
minn = dis[i];
now = i;
}
}
ans += minn;
for(int i = head[now]; i; i = e[i].next) {
int v = e[i].to;
if(dis[v] > e[i].val && !vis[v]) {
dis[v] = e[i].val;
}
}
}
cout << ans << '\n';
return 0;
}建立一个超级源点，将它往每个点建一条边权为\(wi\)的边，跑最小生成树即可
建一个最大生成树，然后跑树上倍增
菜死我了，还没看
这个就不多说了吧……求多源最短路，四行代码搞定，复杂度\(O(N^3)\)
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);另外说一下，用玄学优化是可以让\(floyd\)跑过最短路这个题的！
//早期代码没空格hhh
#include<bits/stdc++.h>
using namespace std;
long long g[1010][1010];
long long n,m,a,b,s;
int qread()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main() {
n=qread();m=qread();
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
g[i][j]=0xffffff;
}
}
for(int i=1; i<=m; ++i) {
a=qread();b=qread();s=qread();
g[a][b]=s;
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
if(i!=k && g[i][k]!=0xffffff) {
for(int j=1; j<=n; j++) {
if(i!=j&&j!=k&&g[i][j]>g[i][k]*g[k][j]) {
g[i][j]=g[i][k]*g[k][j];
}
}
}
printf("%lld",g[1][n]%9987);
return 0;
}\(Dijkstra\)用于求单源最短路径，他是比较优秀的最短路算法，但是不能处理负边权，不做详细介绍
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 5011;
int n, m, ans;
int dis[N], a[N][N];
bool vis[N];
int main() {
memset(a, 0x3f, sizeof(a));
n = read(), m = read();
for(int i = 1, u, v, w; i <= m; i++) {
u = read(), v = read(), w = read();
a[u][v] = a[v][u] = w;
}
for(int i = 0; i <= n; i++) dis[i] = a[1][i];
vis[1] = 1;
dis[1] = 0;
for(int i = 1; i <= n; i++) {
int k = 0;
for(int j = 1; j <= n; j++) {
if(!vis[j] && dis[j] < dis[k]) {
k = j;
}
}
vis[k] = 1;
for(int j = 1; j <= n; j++) {
if(dis[j] > dis[k] + a[k][j]) {
dis[j] = dis[k] + a[k][j];
}
}
}
cout << dis[n] << '\n';
return 0;
}priority_queue <pin> Q;
inline void dij(int st) {
memset(dis, 0x3f, sizeof(dis));
Q.push(pin(dis[st] = 0LL, st));
for(; !Q.empty(); ) {
int x = Q.top().second;
Q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(dis[y] > dis[x] + e[i].val) {
dis[y] = dis[x] + e[i].val;
Q.push(pin(-dis[y], y));
}
}
}
}一个最可怕的最短路算法，因为它的复杂度是错的，甚至很多人都说，\(SPFA\)已经死了，实在是可怕啊
不过\(SPFA\)可以判断负环，这是好的
平常没有负边权还是不要写\(SPFA\)，好好写\(Dijkstra\)吧
queue <int> q;
bool inq[N];
int dis[N], len[N];
bool spfa() {//true表示有环
for(int i = 2; i <= n; i++) dis[i] = INF;
len[1] = 1;
q.push(1);
inq[1] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for(int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
int w = W[u][i];
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
len[v] = len[u] + 1;
if(len[v] >= n) return true;
if(!inq[v]) q.push(v), inq[v] = true;
}
}
}
return false;
}\(floyd\)优化版，按时间走就行了
原文：https://www.cnblogs.com/loceaner/p/11350271.html