1.背包问题
（1）01背包，每个物品只有一个f[i][j]=max(f[i-1][j],f[i-1][j-v]+w)
（2）完全背包 每个物品无限使用f[i][j]=max(f[i-1][j],f[i][j-kv]+kw)
（3）完全背包 每个物品有多个 f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+kw[i]);数多：(先化组，在看成01背包)
（4）分组背包 每组物品有若干个，同一组内的物品最多只能选一个。
分享
二分图
二分图：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。
染色法
看成树，一层0一层1，如果不符合不是二分图
1. 对每个点进行染色
2. 枚举该点的所有出边到达的点，染上不一样的颜色
3. 如果存在奇数环，就不存在二分图
dfs版本
代码思路：
染色可以使用1和2区分不同颜色，用0表示未染色
遍历所有点，每次将未染色的点进行dfs, 默认染成1或者2
由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能立刻break/return
染色失败相当于至少存在2个点染了相同的颜色
染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图
时间复杂度是 O(n+m), n 表示点数，m 表示边数
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}
return true;
}
bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}
题目描述
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。
数据范围
1≤n,m≤105
样例
4 4
1 3
1 4
2 3
2 4
输出
Yes
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010 * 2;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int color[N];//保存各个点的颜色，-1未染色，1 是红色，2 是黑色
int n, m;//点和边
void add(int a, int b)//邻接表插入点和边
{
e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}
bool dfs(int u, int c)//深度优先遍历
{
color[u] = c;//u的点成 c 染色
//遍历和 u 相邻的点
for(int i = h[u]; i!= -1; i = ne[i])
{
int b = e[i];
if(color[b]==-1)//相邻的点没有颜色,则递归处理这个相邻点
{
if(!dfs(b, 3 - c)) return false;//（3 - 1 = 2， 如果 u 的颜色是2，则和 u 相邻的染成 1）
//（3 - 2 = 1， 如果 u 的颜色是1，则和 u 相邻的染成 2）
}
else if( color[b] == c)//如果已经染色，判断颜色是否为 3 - c
{
return false;//如果不是，说明冲突，返回
}
}
return true;
}
int main()
{
memset(h, -1, sizeof h);//初始化邻接表
cin >> n >> m;
for(int i = 1; i <= m; i++)//读入边
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
memset(color, -1, sizeof color);
for(int i = 1; i <= n; i++)//遍历点
{
if(color[i]==-1)//如果没染色
{
if(!dfs(i, 1))//染色该点，并递归处理和它相邻的点
{
cout << "No" << endl;//出现矛盾，输出NO
return 0;
}
}
}
cout << "Yes" << endl;//全部染色完成，没有矛盾，输出YES
return 0;
}
匈牙利算法（求最大匹配）
思路
如果你想找的妹子已经有了男朋友，
你就去问问她男朋友，
你有没有备胎，
把这个让给我好吧
匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配
时间复杂度是 O(nm), n 表示点数，m 表示边数
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
题目描述
给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1、 n2 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105
样例
输入样例：
2 2 4
1 1
1 2
2 1
2 2
输出样例：
2
#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 100010;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool find(int x)
{
//枚举这个男生看上的全部女生
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
//这个女生没有男生考虑
if(!st[j])
{
//表示这个女生已经考虑过
st[j]=true;
//如果这个女生没有男生匹配或者这个女生的男朋友可以找到备胎
if(match[j]==0||find(match[j]))
{
match[j]=x;
return true;
}
}
}
return false;
}
int main()
{
cin>>n1>>n2>>m;
memset(h,-1,sizeof h);
//建立邻接表
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
}
//表示匹配数
int res=0;
//枚举每一个男生
for(int i=1;i<=n1;i++)
{
//把女生全部考虑一遍
memset(st,0,sizeof st);
if(find(i)==true) res++;
}
cout<<res<<endl;
return 0;
}
生成树：一个来连通图的最小连通子图，n个顶点的连通图有n个顶点n-1个边
最小生成树就是权值最小的数
树是所有的点连通，图是点到点。
prim稠密图，Kruskal算法稀疏图
不过Kruskal算法yyds都适用
朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树
时间复杂度是 O(n2+m), n 表示点数，m 表示边数
大佬链接
https://www.acwing.com/solution/content/38312/
朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树
时间复杂度是 O(n2+m), n 表示点数，m 表示边数
确定一个点找与它相连的最短边，和Dijkstra思路一样
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;
}
Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树
时间复杂度是 O(mlogm), n 表示点数，m 表示边数
Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树
时间复杂度是 O(mlogm), n 表示点数，m 表示边数
先把边排序，挨个找最小边，用到了并查集
1. 将每条边从小到大排序
2. 枚举每条边，如果不在一个集合就合并集合
3. res 表示最小生成树权重之和
4. cnt 表示已加入集合的边数
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 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;
}
prim
联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离
与dijkstra一样只是在距离的时候一个+到起始点的距离一个没有。
题目描述
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过10000。
输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
#include<bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n,m;
int g[N][N],dist[N];
bool st[N];
int prim()
{
memset(dist,0x3f,sizeof dist);//初始化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[j]<dist[t]))
t=j;
if(i!=0&&dist[t]==INF) return INF;//,最近的点无穷说明点不连通，直接返回INF
if(i!=0) res+=dist[t];//提前加上防止自环，并将该点加入集合
st[t]=true;
for(int j=1;j<=n;j++) //用该点更新其他点到集合的距离
dist[j]=min(dist[j],g[t][j]);
}
return res;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
//邻接矩阵，取较小边
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
int t=prim();//用t提前存储，防止prim()运行两次
if(t==INF) cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}
Kruskal
大佬连接
https://www.acwing.com/solution/content/104383/
算法思路：
将所有边按照权值的大小进行升序排序，然后从小到大一一判断。
如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。
直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为：使用并查集。
在初始状态下给各个个顶点在不同的集合中。、
遍历过程的每条边，判断这两个顶点的是否在一个集合中。
如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int 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;//res权重之和cnt多少边
for(int i=0; i<m; i++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
if(find(a)!=find(b))//判断两者是否连通，若不连通则
{
p[find(a)] = find(b);//两个集合合并
res += w;//res加的是，最小生成树边的权重之和
cnt++;//当前加入多少边
}
}
if(cnt < n-1) return INF;//判断一共加了多少条边，若是cnt小于n-1则说明不连通
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0; i<m; i++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
int t = kruskal();
if(t == INF) puts("impossible");
else printf("%d\n", t);
}
分享
最短路总结
https://www.acwing.com/solution/content/6976/
负环和回路的影响：邻接表没有影响，邻接矩阵，初始化0x3f，用点求距离
，在DJ里面是点来求距离，可以忽略，spfa优先队列，忽略，ford忽略，
多源里面不能忽略，先排除自环（不存在负权回路)
Dijkstra-朴素 O(n2)O(n2)
1.初始化距离数组, dist[1] = 0, dist[i] = inf;
2.for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
3.将不在S中dist_min的点->t
4.t->S加入最短路集合
5.用t更新到其他点的距离
Dijkstra-堆优化 O(mlogm)O(mlogm)
1.利用邻接表，优先队列
2.在priority_queue<PII,vector<PII>,greater<PII>> heap;中将返回堆顶
3.利用堆顶来更新其他点，并加入堆中类似宽搜
Bellman_ford O(nm)O(nm)
注意连锁想象需要备份, struct Edge{int a,b,c} Edge[M];
1.初始化dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
2.松弛k次，每次访问m条边
Spfa O(n)∼O(nm)O(n)∼O(nm)
1.利用队列优化仅加入修改过的地方
2.for k次
3.for 所有边利用宽搜模型去优化bellman_ford算法
4.更新队列中当前点的所有出边
Floyd O(n3)O(n3)
1.初始化d
2.k, i, j 去更新d
spfa已死 只要是正权边就会卡成Bellman-Ford
spfa判断负环
判断负环的时候都放进去，不一定从那个点开始，五个点有四条边--当边数>=n的时候一定有负环。
spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
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;
}
floyd算法
floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3), n 表示点数
初始化：
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]);
}
题目描述
题目描述
给定一个 nn 个点的有向图，请求出图中是否存在从顶点 11 出发能到达的负环。
负环的定义是：一条边权之和为负数的回路。
输入格式
本题单测试点有多组测试数据。
输入的第一行是一个整数 TT，表示测试数据的组数。对于每组数据的格式如下：
第一行有两个整数，分别表示图的点数 nn 和接下来给出边信息的条数 mm。
接下来 mm 行，每行三个整数 u, v, w。
若 w \geq 0w≥0，则表示存在一条从 u 至 vv边权为 ww的边，还存在一条从 v 至 u 边权为 w 的边。
若 w < 0w<0，则只表示存在一条从 u 至 vv 边权为 w 的边。
输出格式
对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。
样例
输入：
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出
NO
YES
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N], cnt[N];//记录每个点到起点的边数，当cnt[i] >= n 表示出现了边数>=结点数
//，必然有环，而且一定是负环！
bool st[N];//判断当前的点是否已经加入到队列当中了；
//意味着，st数组起着提高效率的作用，不在乎效率的话，去掉也可以
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa()
{
//初始化所有非起点和起点的距离
// memset(dist, 0x3f, sizeof dist);
// dist[1] = 0;
// 这里不需要初始化dist数组为 正无穷。不用初始化的原因是,如果存在负环那么dist不管初始化为多少都会被更新
//定义队列，起点进队, 标记进队
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();
//t出队，标记出队
st[t] = false;
//更新与t邻接的边
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];//结点j可以通过中间点t降低距离
cnt[j] = cnt[t] + 1;//那么结点j在中间点t的基础上加一条到自己的边
if (cnt[j] >= n) return true;//边数不小于结点数，出现负环，函数结束
if (!st[j])//若此时j没在队列中，则进队。已经在队列中了，上面已经更新了数值。重复加入队列降低效率
{
//j进队，标记进队
q.push(j);
st[j] = true;
}
}
}
}
return false;//走到这了，函数还没结束，意味着边数一直小于结点数，不存在负环
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
if (spfa()) puts("Yes");
else puts("No");
return 0;
}
floyd算法
floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3), n 表示点数
初始化：
d[N][N]代表距离
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;
或者
memset(d,INF,sizeof d);
for(int i=1;i<=n;i++)d[i][i]=0;
// 算法结束后，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]);
}
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数n，m，k
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。
输出格式
共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。
数据范围
1≤n≤200,
1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
#include<bits/stdc++.h>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n,m,q;
int d[N][N];//距离
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]);
}
int main()
{
cin>>n>>m>>q;
memset(d,0x3f,sizeof d);//初始化d数组
for(int i=1;i<=n;i++) d[i][i]=0;//防止自环，取最小数0，
while(m--) //邻接矩阵，取权值较小的边
{
int a,b,c;
cin>>a>>b>>c;
d[a][b]=min(d[a][b],c);
}
floyd();
while(q--)
{
int a,b;
cin>>a>>b;
if(d[a][b]>INF/2) cout<<"impossible"<<endl;
else cout<<d[a][b]<<endl;
}
return 0;
}
SPFA也可以在都是正权值使用，怕时间复杂度卡，最大O（mn）
二者可以判断负环，但存在负环不求最短路。
ford存在负环的时候可以用边数作为限制剔除负环的影响
Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路
时间复杂度 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];//存边要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 ++ )//n为次数
{
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];
}
# spfa算法
spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O，最坏情况下 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];
}
用更新的点更新其他点
1. 初始化dist数组和队列q
2. st表示该点在队列中，用于提速
3. 取出队头，更新该点的所有出边，如果可以更新就放到队列中
# 判断负环
spfa判断图中是否存在负环 —— 模板题 AcWing 852. 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;
}
dist[b] = min(dist[b], backup[a] + w);
注意：back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点
1. 迭代 k 次就可以得到不经过 k 次的最短路
2. 要准备 backup 数组，这样就会只更新当前点能到达的所有点，就不会发生串联效应
3. 注意：INF - 1 < INF, 但 INF + 1 == INF
4. 因为有负权边，所以只需判断 bellman_ford() >= INF / 2 即可
ford
给定一个 n 个点 m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 mm 行，每行包含三个整数 x,y,zx,y,z，表示存在一条从点 xx 到点 yy 的有向边，边长为 zz。
点的编号为 1∼n。
输出格式
输出一个整数，表示从 1 号点到 nn号点的最多经过 k条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n1≤x,y≤n，
任意边长的绝对值不超过 10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
思路：
Bellman-Ford基本过程,有k的限制必须使用Ford算法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 10010;
struct Edge {
int a;
int b;
int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++) {//k次循环
memcpy(back, dist, sizeof dist);
for (int j = 0; j < m; j++) {//遍历所有边
int a = e[j].a, b = e[j].b, w = e[j].w;
dist[b] = min(dist[b], back[a] + w);
//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;//注意为0x3f/2;有负环可能趋近于无穷；
else return dist[n];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
e[i] = {a, b, w};
}
int res = bellman_ford();
if (res == -1) puts("impossible");
else cout << res;
return 0;
}
spfa
spfa求最短路正权图也可以.
spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O，最坏情况下 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];
}
用更新的点更新其他点
1. 初始化dist数组和队列q
2. st表示该点在队列中，用于提速
3. 取出队头，更新该点的所有出边，如果可以更新就放到队列中
题目描述
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出”impossible”。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; //储存当前点到起点的距离
bool st[N]; //当前点是否在队列当中，防止存重复的点
void add(int a, int b, int c)//邻接表
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; //起点距自己的距离为 0
queue<int> q;
q.push(1); //起点加入队列
st[1] = true; //起点在队列里了
while (q.size()) //如果队列不空
{
int t = q.front(); //取出队头
q.pop(); //删掉队头
st[t] = false;//这个点已经不在队列里边了
for (int i = h[t]; i != -1; i = ne[i]) //更新 t 的所有邻边
{
int j = e[i]; //取出当前邻边的节点，在这步消除了重边
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) //如果 j 不在队列里边
{
q.push(j); //加入队列
st[j] = true; //在队列里了
}
}
}
}
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int t = spfa();
if (t == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", t);
return 0;
}
一个图中，顶点数n,边数m，当n^2>>m，为稀疏–堆优化m–n)一个级别（100 100）邻接表
当m相对较大时为稠密图。*朴素的*（m–n^2)一个级别（100 10000）邻接矩阵
不超过k条边，BELLMAN
单源只有一个起点，到其他点的最短路
多源 多个点的最短路
朴素dijkstra算法
详细的推到
https://www.acwing.com/solution/content/38318/
朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
时间复杂是 O(n2+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 ++ )//n次迭代，每次寻找不在s中距离最近的点t
{
int t = -1; //不存在负值所以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]);//g[t][j]就是节点t可以到的路径里面最小值
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;//路径不存在
return dist[n];
}
堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
时间复杂度 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];
}
Dijkstra求最短路 I
题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
单源且均为正值用Dijkstra算(m,n^2)，
1.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];//邻接矩阵
int dist[N];//1号点到其他点的距离
bool st[N];//st[i], 第i个点是否确定, 归入s集合中
int dijkstra(){
memset(dist, 0x3f, sizeof dist);//初始化所有点到一号点的距离为正无穷
dist[1] = 0;//初始化第一个点到自己的距离是0
for(int i = 0; i < n - 1; i++)//迭代n - 1次
{
int t = -1;//t = -1表示还没有点, t: 不在集合s中的离一号点距离最近的点
for(int j = 1; j <= n; j++)//找到不在集合s中与一号点距离最近的点
if(!st[j] && (t == -1 || dist[t] > dist[j]))//如果j不在集合s中且 (还没有点或者当前t这个点不是离一号点最短的点)
t = j;
//执行完之后t就是不在集合s中距离一号点最近的点
st[t] = true;//把t存入集合s中
for(int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);//本来应该是用t更新
//其他不在集合s中的点的距离
//但是这里直接用t更新全部点的距离，这是因为已经确定距离的点不会受t的影响。
//因为dist[j] = min(dist[j], dist[t] + g[t][j]);
//对于已经确定了最短距离的点dist[j] <= dist[t]恒成立，这是由t的定义决定的
//对于t 和 j这两个点，j 是比 t 先确定最短距离的点，因此dist[j]一定小于dist[t]
//况且dist[t]还要加一个g[t][j]那么这个值就更大了
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);//读入点数和边数
//存在重边和自环，重边的话保留最短的一条就行了，自环直接忽略掉
memset(g, 0x3f, sizeof g);//初始化点与点之间的距离为正无穷 包括自己到自己也是正无穷
//这里不必纠结自己到自己的距离是0还是正无穷因为只有在用t更新时 j = t才会用到g[t][t]自己到自己的距离，且dist[t] = min(dist[t], dist[t] + g[t][t])
//从公式可以看出g[t][t] = 0或正无穷dist[t]都不变
while (m -- ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);//重边保留长度最短的那条边
}
printf("%d\n", dijkstra());
return 0;
}
2.
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N]; //为稠密阵所以用邻接矩阵存储
int dist[N]; //用于记录每一个点距离第一个点的距离
bool st[N]; //用于记录该点的最短距离是否已经确定
int n,m;
int Dijkstra()
{
memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大
dist[1]=0; //第一个点到自身的距离为0
for(int i=0;i<n;i++) //有n个点所以要进行n次 迭代
{
int t=-1; //t存储当前访问的点
for(int j=1;j<=n;j++) //这里的j代表的是从1号点开始
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
st[t]=true; //该点被遍历
for(int j=1;j<=n;j++) //依次更新每个点所到相邻的点路径值
dist[j]=min(dist[j],dist[t]+g[t][j]);//g[t][j]就是t点到其他的距离
}
if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径
return dist[n];
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g); //邻接矩阵的初始化，由于求的是最小值，因此初始为无穷大
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边
}
cout<<Dijkstra()<<endl;
return 0;
}
2.稀疏图–>邻接表
给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 11 号点到 nn 号点的最短距离，如果无法从 11 号点走到 nn 号点，则输出 −1−1。
输入格式
第一行包含整数 nn 和 mm。
接下来 mm 行每行包含三个整数 x,y,zx,y,z，表示存在一条从点 xx 到点 yy 的有向边，边长为 zz。
输出格式
输出一个整数，表示 11 号点到 nn 号点的最短距离。
如果路径不存在，则输出 −1−1。
数据范围
1≤n,m≤1.5×1051≤n,m≤1.5×105,
图中涉及边长均不小于 00，且不超过 1000010000。
数据保证：如果最短路存在，则最短路的长度不超过 109109。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
思路
这题和 Dijkstra求最短路IDijkstra求最短路I 思路是一样的，就是把枚举选哪个点改成用优选队列来维护最短的长度，还要把迭代换成优先队列是否为空即可。
用堆来优化，就是优化点更新
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//堆的头文件
using namespace std;
typedef pair<int, int> PII;//堆里存储距离和节点编号
const int N = 1e6 + 10;
int n, m;//节点数量和边数
int h[N], w[N], e[N], ne[N], idx;//邻接矩阵存储图
int dist[N];//存储距离
bool st[N];//存储状态
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);//距离初始化为无穷大
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆
heap.push({0, 1});//插入距离和节点编号
while (heap.size())
{
auto t = heap.top();//取距离源点最近的点
heap.pop();
int ver = t.second, distance = t.first;//ver:节点编号，distance:源点距离ver 的距离
if (st[ver]) continue;//如果距离已经确定，则跳过该点
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});//距离变小，则入堆
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
分享
拓扑排序
思路：
1. 看这个图是否有环，如果没有环就一定存在拓扑序列
2. 求出每个点的入度
3. 把所有入度为 0 的点入队
4. 枚举每一条边，删除它就是让 d[j] --;
5. 当入度为 0 时，说明前面的点都已经有序，将当前点入队
6. 当所有点都入队时说明存在拓扑序列
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;
}
题目描述
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
样例
3 3
1 2
2 3
1 3
输出
123
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort()
{
int hh=0,tt=-1;
for(int i=1;i<=n;i++)//把所有入度为0的点入队
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];
d[j]--;//入度减一
if(d[j]==0)
q[++tt]=j;
}
}
//当所有点入队时，说明存在拓扑序列
return tt==n-1;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
//建边，并且b的入度加1
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;//a->b所以b的入度加一
}
//若为真，说明所有点都已入队
if(topsort())
for(int i=0;i<n;i++)
cout<<q[i]<<' ';
else cout<<-1<<endl;
return 0;
}
2.STL
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N;
int n, m;
int h[N], e[M], ne[M], idx;
int d[N]; //入度
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void topsort() {
queue<int> q;
int ans[N], top = 0;
for (int i = 1; i <= n; i++)
if (!d[i]) q.push(i), ans[++top] = i;
while (q.size()) {
int t = q.front(); q.pop();
for (int i = h[t]; ~i ; i = ne[i]) {
int j = e[i];
if (--d[j] == 0) q.push(j), ans[++top] = j;
}
}
if (top != n) puts("-1");
else for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m--) {
int a, b; scanf("%d%d", &a, &b);
add(a, b); d[b]++;
}
topsort();
return 0;
}
分享
树与图的存储
树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
(2) 邻接表：
和哈希表的拉链法类似。
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
树与图的遍历
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
题目描述
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数n，表示树的结点数。
接下来n-1行，每行包含两个整数a和b，表示点a和点b之前存在一条边。
输出格式
输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。
数据范围
1≤n≤105
样例
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4
结论
在本题的邻接表存储结构中，有两个容易混淆的地方，一个是节点的编号，一个是节点的下标。
节点的编号是指上图所画的树中节点的值，范围是从1~n。在本题中，每次输入的a和b就是节点的编号，编号用e[i]数组存储。
节点的下标指节点在数组中的位置索引，数组之间的关系就是通过下标来建立连接，下标用idx来记录。idx范围从0开始，如果idx==-1表示空。
1:->4->7->2
2:->5->8->1
e[i]的值是编号，是下标为i节点的编号,如例1：e[0]=4,e[1]=7,e[2]=2。
ne[i]的值是下标，是下标为i的节点的next节点的下标,e[0]=2,e[1]=3;e[3]=-1。
h[i]存储的是下标，是编号为i的节点的next节点的下标，比如编号为1的节点的下一个节点是4，那么我输出e[h[1]]就是4h[1]=0,e[h[1]]=4;
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边
int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //表示重心的所有的子树中，最大的子树的结点数目
bool st[N]; //记录节点是否被访问过，访问过则标记为true
//a所对应的单链表中插入b a作为根
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;//插在头节点，a为根可以到的点，最前面,不同于链表比较方便
}
// dfs 框架
/*
void dfs(int u){
st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]) {
dfs(j);
}
}
}
*/
//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
st[u] = true; //标记访问过u节点
int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点
//访问u的每个子节点
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];//用e[i]来存储节点的数值，取出来
if (!st[j]) {//因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
int s = dfs(j); // u节点的单棵子树节点数 如图中的size值
res = max(res, s); // 记录最大联通子图的节点数,就是取出u以后两个的最大值
sum += s; //以j为根的树 的节点数
}
}
//n-sum 如图中的n-size值，不包括根节点；
res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
return sum;//返回以u为根的子树中节点的个数，包括u。
}
int main() {
memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
cin >> n; //表示树的结点数
// 题目接下来会输入，n-1行数据，
for (int i = 0; i < n - 1; i++) { // 树中是不存在环的，对于有n个节点的树，必定是n-1条边
int a, b;
cin >> a >> b;
add(a, b), add(b, a); //无向图
}
dfs(1); //可以任意选定一个节点开始 u<=n。选择的节点，不是位置
cout << ans << endl;
return 0;
}
树与图的广度优先遍历
2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
题目描述(图中点的层次)
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
数据范围
1≤n,m≤105
输入样例
4 5
1 2
2 3
3 4
1 3
1 4
输出样例
1
1.模拟数组
#include <cstring>
#include <iostream>
using namespace std;
const int N=1e5+10;
int h[N], e[N], idx, ne[N];
int d[N]; //存储每个节点离起点的距离 d[1]=0
int n, m; //n个节点m条边
int q[N]; //存储层次遍历序列 0号节点是编号为1的节点
void add(int a, int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
int hh=0,tt=0;
q[0]=1; //0号节点是编号为1的节点,可以换点，是拉链法换对头
memset(d,-1,sizeof d);//先初始化，在赋值d[n]=0;要不然少一。
d[1]=0; //存储每个节点离起点的距离 从1号节点开始，距离为0,从2开始，d[2]=0
//当我们的队列不为空时
while(hh<=tt)
{
//取出队列头部节点
int t=q[hh++];
//遍历t节点的每一个邻边
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
//如果j没有被扩展过
if(d[j]==-1)
{
d[j]=d[t]+1; //d[j]存储j节点离起点的距离，并标记为访问过
q[++tt] = j; //把j结点 压入队列
}
}
}
return d[n];
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs()<<endl;
}
2.stl
#include<iostream>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
memset(d,-1,sizeof d);宽搜模板，如果换点就换对头，d[x]=0,也改变
queue<int> q;
d[1]=0;
q.push(1);
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(d[j]==-1)
{
d[j]=d[t]+1;
q.push(j);
}
}
}
return d[n];
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
printf("%d ",bfs());
return 0;
}
2.模板
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],h[N],d[N],idx;
int m,n;
bool st[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs()
{
queue<int>q;
q.push(1);
st[1]=true;
memset(d,-1,sizeof d);
d[1]=0;
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
d[j]=d[t]+1;
st[j]=true;
q.push(j);
}
}
}
return d[m];
}
int main()
{
cin>>m>>n;
memset(h,-1,sizeof h);
while(n--)
{
int a,b;
cin>>a>>b;
add(a,b);
}
printf("%d",dfs());
return 0;
}
希望更丰富的展现？使用 Markdown、LaTeX 公式。
hhh，还在看背包九讲，先列个大纲