写点什么

来自北京大学 NOIP 金牌选手 yxc 的常用代码模板 3——搜索与图论

  • 2021 年 11 月 12 日
  • 本文字数:2996 字

    阅读完需:约 10 分钟

}


}


}

3.拓扑排序

时间复杂度 O(n+m), n表示点数,m 表示边数


bool topsort()


{


int hh = 0, tt = -1;


// d[i] 存储点 i 的入度


for (int i = 1; i <= n; i ++ )


if (!d[i])


q[ ++ tt] = i;


while (hh <= tt)


{


int t = q[hh ++ ];


for (int i = h[t]; i != -1; i = ne[i])


{


int j = e[i];


if (-- d[j] == 0)


q[ ++ tt] = j;


}


}


// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。


return tt == n - 1;


}

4.朴素 dijkstra 算法

时间复杂是 O(n^2+m) n 表示点数,m 表示边数


int g[N][N]; // 存储每条边


int dist[N]; // 存储 1 号点到每个点的最短距离


bool st[N]; // 存储每个点的最短路是否已经确定


// 求 1 号点到 n 号点的最短路,如果不存在则返回-1


int dijkstra()


{


memset(dist, 0x3f, sizeof dist);


dist[1] = 0;


for (int i = 0; i < n - 1; i ++ )


{


int t = -1; // 在还未确定最短路的点中,寻找距离最小的点


for (int j = 1; j <= n; j ++ )


if (!st[j] && (t == -1 || dist[t] > dist[j]))


t = j;


// 用 t 更新其他点的距离


for (int j = 1; j <= n; j ++ )


dist[j] = min(dist[j], dist[t] + g[t][j]);


st[t] = true;


}


if (dist[n] == 0x3f3f3f3f) return -1;


return dist[n];


}

5.堆优化版 dijkstra

时间复杂度 O(mlogn), n表示点数,m 表示边数


typedef pair<int, int> PII;


int n; // 点的数量


int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边


int dist[N]; // 存储所有点到 1 号点的距离


bool st[N]; // 存储每个点的最短距离是否已确定


// 求 1 号点到 n 号点的最短距离,如果不存在,则返回-1


int dijkstra()


{


memset(dist, 0x3f, sizeof dist);


dist[1] = 0;


priority_queue<PII, vector<PII>, greater<PII>> heap;


heap.push({0, 1}); // first 存储距离,second 存储节点编号


while (heap.size())


{


auto t = heap.top();


heap.pop();


int ver = t.second, distance = t.first;


if (st[ver]) continue;


st[ver] = true;


for (int i = h[ver]; i != -1; i = ne[i])


{


int j = e[i];


if (dist[j] > distance + w[i])


{


dist[j] = distance + w[i];


heap.push({dist[j], j});


}


}


}


if (dist[n] == 0x3f3f3f3f) return -1;


return dist[n];


}

6.Bellman-Ford 算法

时间复杂度 O(nm), n 表示点数,m 表示边数


int n, m; // n 表示点数,m 表示边数


int dist[N]; // dist[x]存储 1 到 x 的最短路距离


struct Edge // 边,a 表示出点,b 表示入点,w 表示边的权重


{


int a, b, w;


}edges[M];


// 求 1 到 n 的最短路距离,如果无法从 1 走到 n,则返回-1。


int bellman_ford()


{


memset(dist, 0x3f, sizeof dist);


dist[1] = 0;


// 如果第 n 次迭代仍然会松弛三角不等式,就说明存在一条长度是 n+1 的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。


for (int i = 0; i < n; i ++ )


{


for (int j = 0; j < m; j ++ )


{


int a = edges[j].a, b = edges[j].b, w = edges[j].w;


if (dist[b] > dist[a] + w)


dist[b] = dist[a] + w;


}


}


if (dist[n] > 0x3f3f3f3f / 2) return -1;


return dist[n];


}

7.spfa 算法(队列优化的 Bellman-Ford 算法)

时间复杂度 平均情况下 O(m),最坏情况下 O(nm), n表示点数,m 表示边数


int n; // 总点数


int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边


int dist[N]; // 存储每个点到 1 号点的最短距离


bool st[N]; // 存储每个点是否在队列中


// 求 1 号点到 n 号点的最短路距离,如果从 1 号点无法走到 n 号点则返回-1


int spfa()


{


memset(dist, 0x3f, sizeof dist);


dist[1] = 0;


queue<int> q;


q.push(1);


st[1] = true;


while (q.size())


{


auto t = q.front();


q.pop();


st[t] = false;


for (int i = h[t]; i != -1; i = ne[i])


{


int j = e[i];


if (dist[j] > dist[t] + w[i])


{


dist[j] = dist[t] + w[i];


if (!st[j]) // 如果队列中已存在 j,则不需要将 j 重复插入


{


q.push(j);


st[j] = true;


}


}


}


}


if (dist[n] == 0x3f3f3f3f) return -1;


return dist[n];


}

8.spfa 判断图中是否存在负环

时间复杂度是 O(nm), n 表示点数,m表示边数


int n; // 总点数


int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边


int dist[N], cnt[N]; // dist[x]存储 1 号点到 x 的最短距离,cnt[x]存储 1 到 x 的最短路中经过的点数


bool st[N]; // 存储每个点是否在队列中


// 如果存在负环,则返回 true,否则返回 false。


bool spfa()


{


// 不需要初始化 dist 数组


// 原理:如果某条最短路径上有 n 个点(除了自己),那么加上自己之后一共有 n+1 个点,由抽屉原理一定有两个点相同,所以存在环。


queue<int> q;


for (int i = 1; i <= n; i ++ )


{


q.push(i);


st[i] = true;


}


while (q.size())


{


auto t = q.front();


q.pop();


st[t] = false;


for (int i = h[t]; i != -1; i = ne[i])


{


int j = e[i];


if (dist[j] > dist[t] + w[i])


{


dist[j] = dist[t] + w[i];


cnt[j] = cnt[t] + 1;


if (cnt[j] >= n) return true; // 如果从 1 号点到 x 的最短路中包含至少 n 个点(不包括自己),则说明存在环


if (!st[j])


{


q.push(j);


st[j] = true;


}


}


}


}


return false;


}

9.floyd 算法

时间复杂度是 O(n3)O(n3), nn 表示点数


初始化:


for (int i = 1; i <= n; i ++ )


for (int j = 1; j <= n; j ++ )


if (i == j) d[i][j] = 0;


else d[i][j] = INF;


// 算法结束后,d[a][b]表示 a 到 b 的最短距离


void floyd()


{


for (int k = 1; k <= n; k ++ )


for (int i = 1; i <= n; i ++ )


for (int j = 1; j <= n; j ++ )


d[i][j] = min(d[i][j], d[i][k] + d[k][j]);


}

10.朴素版 prim 算法

时间复杂度是 O(n2+m), n 表示点数,m 表示边数


int n; // n 表示点数


int g[N][N]; // 邻接矩阵,存储所有边


int dist[N]; // 存储其他点到当前最小生成树的距离


bool st[N]; // 存储每个点是否已经在生成树中


// 如果图不连通,则返回 INF(值是 0x3f3f3f3f), 否则返回最小生成树的树边权重之和


int prim()


{


memset(dist, 0x3f, sizeof dist);


int res = 0;


for (int i = 0; i < n; i ++ )


{


int t = -1;


for (int j = 1; j <= n; j ++ )


if (!st[j] && (t == -1 || dist[t] > dist[j]))


t = j;


if (i && dist[t] == INF) return INF;


if (i) res += dist[t];


st[t] = true;


for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);


}


return res;


}

11.Kruskal 算法

时间复杂度是 O(mlogm), n 表示点数,m 表示边数


int n, m; // n 是点数,m 是边数


int p[N]; // 并查集的父节点数组


struct Edge // 存储边


{


int a, b, w;


bool operator< (const Edge &W)const


{


return w < W.w;


}


}edges[M];


int find(int x) // 并查集核心操作


{


if (p[x] != x) p[x] = find(p[x]);


return p[x];


}


int kruskal()


{


sort(edges, edges + m);


for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集


int res = 0, cnt = 0;


for (int i = 0; i < m; i ++ )


{


int


【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


a = edges[i].a, b = edges[i].b, w = edges[i].w;


a = find(a), b = find(b);


if (a != b) // 如果两个连通块不连通,则将这两个连通块合并


{


p[a] = b;


res += w;


cnt ++ ;


}


}


if (cnt < n - 1) return INF;


return res;


}

12.染色法判别二分图

时间复杂度是 O(n+m), n 表示点数,m 表示边数


int n; // n 表示点数


int h[N], e[M], ne[M], idx; // 邻接表存储图

评论

发布
暂无评论
来自北京大学NOIP金牌选手yxc的常用代码模板3——搜索与图论