1：深度优先搜索去寻找树的重心：
给定一颗树，树中包含 nn 个结点（编号 1∼n1∼n）和 n−1n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 nn，表示树的结点数。
接下来 n−1n−1 行，每行包含两个整数 aa 和 bb，表示点 aa 和点 bb 之间存在一条边。
输出格式
输出一个整数 mm，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤1051≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4考虑的方式是深度优先搜索， 然后考虑到用临接表来储存。
添加临边的操作：
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
代码片段：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e06 + 10;
int idx, h[N], e[N], ne[N];
bool stu[N];
int n, cnt = 1e06;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
int dfs(int u) {
stu[u] = true;
int sum = 1, res = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!stu[j]) {
int s = dfs(j);
sum += s;
res = max(res, s);
}
}
res = max(res, n - sum);
cnt = min(cnt, res);
return sum;
}
int main() {
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i < n; i++){
int a, b;
cin >> a>> b;
add(a, b);
add(b, a);
}
dfs(1);
cout << cnt;
return 0;
}记得要初始化一下h[N]为-1.
宽度优先搜索寻找图中点的层次：
给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 11，点的编号为 1∼n1∼n。
请你求出 11 号点到 nn 号点的最短距离，如果从 11 号点无法走到 nn 号点，输出 −1−1。
输入格式
第一行包含两个整数 nn 和 mm。
接下来 mm 行，每行包含两个整数 aa 和 bb，表示存在一条从 aa 走到 bb 的长度为 11 的边。
输出格式
输出一个整数，表示 11 号点到 nn 号点的最短距离。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1方法是bfs, 其实也不是很难
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e06 + 10;
int h[N], e[N], ne[N], idx;
int d[N];
int n, m;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int bfs() {
queue<int> q;
memset(d, -1, sizeof d);
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() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a>> b;
add(a, b);
}
cout << bfs();
return 0;
}Dijkstra单源最短路无负边的情况：
给定一个 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≤5001≤n≤500,
1≤m≤1051≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010;
int dist[N];
int g[N][N];
bool stu[N];
int n, m;
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 1; i <= n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!stu[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
if (t == n) break;
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
stu[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
memset(g, 0x3f, sizeof g);
cin >> n >> m;
while (m --) {
int a, b, c;
cin >> a>> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << dijkstra();
return 0;
}第二种堆优化：
priority_queue<PII, vector>PII, greater<PII>>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e06 + 10;
typedef pair<int,int> PII;
int h[N], idx, e[N], ne[N], w[N];
int dist[N];
bool stu[N];
int n, m;
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
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, distant = t.first;
if (stu[ver]) continue;
stu[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
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();
return 0;
}