建图(链式前向星)
int h[N],e[N], en[N];//这里的en一般写成ne
int idx;
int w[N];
void add(int a, int b, int c)
{
e[idx] = b;
en[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}寻找距离r点最远的距离
void dfs(int r,int l)
{
for (int i = h[r]; i != -1; i = en[i])//遍历r的所有临边
{
int q = e[i];
if (!st[q])
{
st[q] = true;
int co = w[i];
if (l + co > maxx)
{
far = q;
maxx = l + co;
}
dfs(q, l + co);
}
}
}
二分图判断
当且仅当图中没有奇数环，在所有连通块中，将随机一个点染色，然后dfs遍历连通块，和这个点相连的点染其他颜色，如果颜色相同，那么失败
bool check=true;
for (int i = 1; i <= n; i++) {
if (!color[i]) {
dfs(i, 1);
}
}
void dfs(int a, int b) {
color[a] = b;
for (int i = h[a]; ~i; i = ne[i]) {
if (!color[e[i]]) {
dfs(e[i], 3 - b);//1和2是不同的颜色
} else if (color[e[i]] == b) {
check = false;
return;
}
}
}树遍历
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
根据前中遍历求得后续遍历（存在ans），当无法找到根节点时表示无法完成,根据build的顺序可以决定存储结果是前中后序列遍历
void build1(int ql, int qr, int zl, int zr) {
int root = qianxu[ql];
int k = -1;
for (int i = zl; i <= zr; i++) {
if (zhongxu[i] == root) {
k = i;
break;
}
}
if (k == -1) {
st = false;
return;
} else {
int llen = k - zl;
int rlen = zr - k;
if (llen > 0) {
build1(ql + 1, ql + llen, zl, k - 1);//遍历左子树
}
if (rlen > 0) {
build1(qr - rlen + 1, qr, k + 1, zr);//遍历右子树
}
}
ans.push_back(root);//遍历根
}
//结论：对于任何给定的完全二叉树结点数量，都可以通过数组直接给定，结点数量就是数组长度
最小生成树
遍历n次，每次取出距离连通块最近的没有标记过的点，然后标记该点，通过该点的临边更新其他边，返回最小生成树边总长度。
int prim() {
int ans = 0;
memset(st,0,sizeof(st));
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 (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
st[t] = true;
ans += dist[t];
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], an[t][j]);
}
}
return ans;
}迪杰斯特拉（nlogn）：
基本思想：初始化为{0,n},意思为n到n的距离为0，每次取出优先队列中最小的点，也就是可以确定的最短路径和点，根据这个已经确定的点去更新周围的点，但凡是能更新的，都加入优先队列中，st[i]表示第i点是否已经被确认最短路径了，而且最开始n刚加进去的时候还没有被确认，所以一开始别把n认定为确定的点了。
#define x first
#define y second
typedef pair<int, int> pi;
void djs(int n)
{
memset(dist, 0x3f, sizeof(dist));
memset(st,false,sizeof(st));
priority_queue<pi, vector<pi>, greater<pi>> heap;
dist[n] = 0;
heap.push({ 0,n });
while (heap.size())
{
auto p = heap.top();
heap.pop();
if (st[p.y])
continue;
st[p.y] = true;
for (int u = h[p.y];u != -1; u = ne[u])
{
int a = e[u];//这个点
int dis = w[u];
if (dist[a] > dist[p.y] + dis)
{
dist[a] = dist[p.y] + dis;
heap.push({dist[a],a});
}
}
}
}bellman-ford
int dist[510];
struct Edge {
int a, b, c;
}edge[10010];
int main()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
{
cin >> edge[i].a >> edge[i].b >> edge[i].c;
}
for (int i = 1; i <= k; i++)
{
int distt[510];
memcpy(distt,dist,sizeof(dist));
for (int j = 1; j <= m; j++)
{
int to = edge[j].b;
int pp = edge[j].a;
dist[to] = min(dist[to], distt[pp] + edge[j].c);
}
}
if (dist[n] > 0x3f3f3f3f/2)//重要，比如说5是无穷大，4是无穷大，4-5是-2，那么5会更新为0x3f3f3f3f-2;
cout << "impossible";
else
cout << dist[n];
return 0;
}
spfa
bellman-ford的优化版本，对于含负权也可以用，最坏 O(nm)最好O(m),m是边数，n是边数
基本思想是：初始加入最初点，st[i]表示i是否在queue中，根据queue里面的点依次更新其他所有相邻点，如果一个点被更新了，那么加入队列，注意出队列时要把st改变。
void spfa() {
memset(dist, 0x3f, sizeof(dist));
memset(st,false,sizeof(st));
q.push(1);
dist[1] = 0;
st[1] = true;
while (q.size()) {
int a = q.front();
q.pop();
st[a]=false;
for (int i = h[a]; i != -1; i = ne[i]) {
if (dist[e[i]] > dist[a] + w[i]) {
dist[e[i]] = dist[a] + w[i];
if (!st[e[i]]) {
q.push(e[i]);
st[e[i]]=true;
}
}
}
}
}无向图的最小环（大于等于三个节点）：
在floyd的第k层未开始循环前，已经求解了所有i和j之间经过1k-1的最短路径，为了按照环中的最大点来分类，枚举点k的所有临点i和j（i和j均小于k），如果i和j已经可达，那么i和j之间的点也只是1k-1，满足环中最大点为k，此时环的值为k的两个临边和加上i和j的最短路径长度。
为了按顺序输出方案，可以把方案定为kiget_path(i,j)~j,这里的get_path是i和j的最短路中所有点（不包括i和j），在floyd循环中可以记录最后一个更新i和j距离的点，记为pos[i][j],那么get_path（i,j）可以用分治法，即get_path（i,j）=get_path(i,pos[i][j])+pos[i][j]+get_path(pos[i][j],j),当pos[i][j]==0时意味着i和j的最短路不经过其他点，那么按照get_path（i,j）的定义”i和j的最短路中所有点（不包括i和j）“，就可以直接返回了。
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
typedef long long ll;
int w[110][110], f[110][110];
vector<int> path;
int pos[110][110];
void get_path(int i, int j) {
if (pos[i][j] == 0)
return;
get_path(i, pos[i][j]);
path.push_back(pos[i][j]);
get_path(pos[i][j], j);
}
int main(void) {
int n, m;
cin >> n >> m;
memset(w, 0x3f, sizeof(w));
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
w[a][b] = min(w[a][b], c);
w[b][a] = min(w[b][a], c);
}
for (int i = 1; i <= n; i++)
w[i][i] = 0;
memcpy(f, w, sizeof(w));
int ans = INF;
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++) {
for (int j = i + 1; j < k; j++) {
if ((ll)w[i][k] + w[k][j] + f[i][j] < ans) {
{
ans = w[i][k] + w[k][j] + f[i][j];
path.clear();
path.push_back(k);
path.push_back(i);
get_path(i, j);
path.push_back(j);
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
{
if (f[i][k] + f[k][j] < f[i][j]) {
f[i][j] = f[i][k] + f[k][j];
pos[i][j] = k;
}
}
}
}
}
if(path.size())
{
for (auto i : path)
cout << i << " ";
}
else
cout<<"No solution.\n";
return 0;
}
最短路计数
按照djs来求解过程一定是拓扑序。如果f+w<f，那么最短路数量前赋予给后，如果f+w和f相同那么最短路数量后+前
void djs(int a) {
memset(st, false, sizeof(st));
memset(f, 0x3f, sizeof(f));
priority_queue<pi, vector<pi>, greater<pi>> heap;
heap.push({0, a});
f[a] = 0;
dp[a] = 1;
while (heap.size()) {
pi u = heap.top();
heap.pop();
if (st[u.y])
continue;
st[u.y] = true;
for (int i = h[u.y]; ~i; i = ne[i]) {
if (u.x + w[i] < f[e[i]]) {
f[e[i]] = u.x + w[i];
heap.push({f[e[i]], e[i]});
dp[e[i]] = dp[u.y];//第一次遇到最短路，覆盖掉最短路
} else if (u.x + w[i] == f[e[i]]) {
dp[e[i]] =(dp[e[i]]+ dp[u.y]);//相当于dp
}
}
}
}最短路计数拓展
求每个点的最短路和次短路数量
思路为在djs过程中将每个点分为两部分，f[i][0]是i的最短路长度，f[i][1]是到i的次短路长度，cnt[i][0]是到i的最短路数量，cnt[i][1]是到i的次短路数量。
heap中弹出来的为点+状态的二维表示状态，所以判断是否出现也是点+状态的二维表示，f[u][type]+w[i]有四种情况，是被f[k][0],f[k][1]隔开的，分别是小于f[k][0]，类比与树形dp，次小值继承前一个最小值的信息；然后是等于f[k][0]和f[k][1],然后是大于f[k][0]小于f[k][1]，注意每一次更新都需要将更新后的二维状态加入heap数组。
struct node {
int dist, u, type;
bool operator>(const node a) const {
return dist > a.dist;
}
};
void djs(int s) {
memset(f, 0x3f, sizeof(f));
memset(st, 0, sizeof(st));
memset(cnt, 0, sizeof(cnt));
priority_queue<node, vector<node>, greater<node>> heap;
heap.push({0, s, 0});
f[s][0] = 0;
cnt[s][0] = 1;
cnt[s][1] = 0;
while (heap.size()) {
node l = heap.top();
heap.pop();
int u = l.u, dist = l.dist, type = l.type;
if (st[u][type])
continue;
st[u][type] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int k = e[i];
if (dist + w[i] < f[k][0]) {
f[k][1] = f[k][0], cnt[k][1] = cnt[k][0];
heap.push({f[k][1], k, 1});
f[k][0] = dist + w[i], cnt[k][0] = cnt[u][type];
heap.push({f[k][0], k, 0});
} else if (dist + w[i] == f[k][0])
cnt[k][0] += cnt[u][type];
else if (dist + w[i] < f[k][1]) {
f[k][1] = dist + w[i], cnt[k][1] = cnt[u][type];
heap.push({f[k][1], k, 1});
} else if (dist + w[i] == f[k][1])
cnt[k][1] += cnt[u][type];
}
}
}
