前言
经过昨天的一天模拟赛，我成功坐牢5小时，13道题就会两道，所以我决定放弃每天的傻逼题和rating赛的题，把时间都用来详细的复习学过的东西
链式前向星存图的补充
之前的好多模板都是用链前写的，链前不会的话一点都看不懂之前的模板，所以还是重新学习一下
void add(int u,int v,int value) {
e[cnt].to = v;
e[cnt].w = value;
e[cnt].nxt = head[u];
head[u] = cnt++;
}
上述代码就是链前的一个正常的加边操作，感觉链前的存图是以边为单位存的，记录了每条边的性质，包括边权，终点等。代码里u，v，value表示从u到v有边权为value的边
值得注意的是，链前的存图是从前往后存的，但是链前的遍历是从后往前遍历的
e[cnt].to = v; 这一条表示第cnt条边通往v点，注意这里cnt是从0开始的
e[cnt].w = value; 存边权
e[cnt].nxt = head[u] 首先，head[u]表示的是，以u为起点的，最后一条边的编号，nxt表示的是和这条边起点相同的上一条边的编号，为什么这么写是因为你新往后存进去了一条边，那上一个最后一条边就变成倒数第二条边了，在你现在存的这条边的前一条。这个nxt好具有迷惑性，刚开始看以前写的代码的时候就被这个迷惑住了，其实感觉这个叫front会贴切很多……
head[u] = cnt++;这个就是更新以u为起点的最后一条边的编号，代码的含义是先head[u]=cnt,然后cnt++
关于初始化：head数组我们将所有元素初始化为-1，待会遍历的时候会比较方便，cnt的值初始化为0，也就是说我们边的编号是从0开始的
for(int i = 1;i <= n; i++) {
printf("%d\n" ,i);
for(int j = head[i];j != -1; j = e[j].nxt) {
printf("%d %d %d\n" ,i,e[j].to,e[j].w);
}
}
图的遍历如上
我们对于每一个点，都可以通过head找到他以这个点为起点的最后一条边，然后通过e[j].nxt往前遍历，因为我们的每一个nxt都是通过head来赋值的，所以最初的那条边过后，nxt值一定会是最原始的head，也就是-1，这个时候停止就行
dijkstra最短路
复杂度O(mlgn)
最短路算法，通过这个算法，我们可以成功得到所有点到出发点的最短路径
dij的核心想法就是：确定当前的路径是最短的，绕路不可能比他更快
所以dij的核心执行方法就是：扫描所有通路，找到距离出发点最近的路，然后判断我是直达快还是从当前点绕路到那个点更快
需要实现这个操作，我们需要两个数组：
一个是judge[]，用来判断当前的点是否已经是最优化结果
一个是dis[],dis[n]记录的是出发点到n点的最短距离，所以我们首先将dis初始化为无穷大，出发点的dis值是0
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pr;
int n,m,s;
priority_queue<pr, vector<pr>,greater<pr> > q; // 优先队列按照first的值排序
struct edge{
int to,nxt,w;
}e[10000001];
int head[1000001];
int cnt = 0;
bool judge[1000001];
int dis[1000001] = { };
void add(int u,int v,int value) {
e[cnt].to = v;
e[cnt].w = value;
e[cnt].nxt = head[u];
head[u] = cnt++;
}
void dij() {
q.push(make_pair(0,s));
while(!q.empty()) {
pr p = q.top();
q.pop();
if(judge[p.second] == true) continue;
judge[p.second] = true;
for(int i = head[p.second];i != -1; i = e[i].nxt) {
if(dis[e[i].to] > dis[p.second] + e[i].w) {
dis[e[i].to] = dis[p.second] + e[i].w;
q.push(make_pair(dis[e[i].to],e[i].to));
}
}
}
}
int main () {
memset(head,-1,sizeof(head));
scanf("%d %d %d" ,&n,&m,&s);
for(int i = 1;i <= m; i++) {
int a,b,c;
scanf("%d %d %d" ,&a,&b,&c);
add(a,b,c);
}
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(judge,false,sizeof(judge));
dis[s] = 0;
dij();
for(int i = 1;i <= n; i++) {
printf("%d " ,dis[i]);
}
return 0;
}
附上实例：
对于这个图，我们从1出发，那么从1我们可以直接到达2，3，6，我们先把2，3，6存入队列，然后距离1直线距离最近的是3，所以我们来看3
3可以到达两个点，5和6，那么我们来看，从3绕路到6是要比从1直接到6快的，所以我们更新dis[6],同理更新dis[5],因为初始化设成了极大值，接下来看5，5可以到达4，8，6，但是6可以通过3更近的到，所以6不动，更新到4和8的距离
接下来看4，4可以到达2，8，通过绕路到4再到2显然是更近的，所以更新2的距离，同理更新8
以此类推，最终可以得到各个点距离起点的最短路
SPFA最短路
这个最短路相对来说比较暴力，根据刚刚dij的想法，我们知道了
如果对于一个点来说，绕路到达下一个点比直接到达下一个点更近，那么我们选择绕路到达下一个点，我们将这个操作叫做松弛
SPFA的基本想法就是，只有一个点在上一轮被松弛成功时，这一轮从这个点连出的点才有可能被成功松弛。
松弛的本质其实是通过一个点中转来缩短距离(如果你看了前置很容易理解)。所以，如果起点到一个点的距离因为某种原因变小了，从起点到这个距离变小的点连出的点的距离也有可能变小(因为可以通过变小的点中转)。
所以SPFA的想法就是反复松弛，把所有上一轮松驰过的点再次放入队列反复松弛，直到队列为空。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pr;
int m,n;
struct edge{
int to;
int nxt;
int w;
}e[1000001];
bool judge[1000001]; //这个judge数组是判断这个点有没有入队，有的话就不用重复入队了
int head[10000001];
int dis[10000001];
int cnt = 0;
int s;
void add(int u,int v,int value) {
e[cnt].w = value;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt++;
}
queue<int>q;
void spfa() {
memset(judge,false,sizeof(judge));
fill(dis+1,dis+n+1,2147483647);
dis[s] = 0;
q.push(s);
while(!q.empty()) {
int now = q.front();
q.pop();
judge[now] = false;
for(int i = head[now];i != -1; i = e[i].nxt) {
int v = e[i].to;
if(dis[v] > dis[now] + e[i].w) {
dis[v] = dis[now] + e[i].w;
if(judge[v] == false) {
q.push(v);
judge[v] = true;
}
}
}
}
}
int main () {
scanf("%d %d %d" ,&n,&m,&s);
memset(head,-1,sizeof(head));
for(int i = 1;i <= m; i++) {
int a,b,c;
scanf("%d %d %d" ,&a,&b,&c);
add(a,b,c);
}
spfa();
for(int i = 1;i <= n; i++) {
printf("%d " ,dis[i]);
}
return 0;
}
SPFA的最差复杂度是O(km),k是每个点的入队次数，根据大佬所说，k平均在4左右，但是有些情况下会被卡到接近n，导致了SPFA的效率不如dij稳定
但是SPFA可以解决掉dij无法解决的问题，就是负环。
负环就是在一个环中，所有边权的合为负数，如果这之后你用dij在里面跑的话，由于根据松弛的条件，函数就会一直在负环里跑，你的最短路就会变成-INF，然后出错。而SPFA也是会一直在负环跑，但是我们可以通过判断每一个点的入队次数来判断是不是有负环，如果一个点入队超过n次，就说明他在里头转的次数太多了，这时候就认为有负环
#include <bits/stdc++.h>
using namespace std;
inline int gin() {
char c = getchar();
int s = 0, f = 1;
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
s = (s << 3) + (s << 1) + (c ^ 48);
c = getchar();
}
return s * f;
}
const int N = 5e3 + 5;
int n, m, cnt[N], d[N], tot = 0, head[N];
bool h[N], t;
queue<int> q;
struct edge {
int dis, ne, to;
} e[N << 1];
inline void add(int u, int v, int w) {
e[++tot].dis = w;
e[tot].to = v;
e[tot].ne = head[u];
head[u] = tot;
}
inline void spfa() {
memset(h, 0, sizeof h);
memset(cnt, 0, sizeof cnt);
memset(d, 63, sizeof d);
h[1] = 1, t = 0, d[1] = 0;
q.push(1);
while (q.size()) {
int u = q.front();
q.pop();
h[u] = 0;
if (cnt[u] == n - 1) {
t = 1;
return;
}
cnt[u]++;
for (int i = head[u]; i; i = e[i].ne) {
int v = e[i].to, w = e[i].dis;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (!h[v])
h[v] = 1, q.push(v);
}
}
}
}
int main() {
int T = gin();
while (T--) {
n = gin(), m = gin();
tot = 0;
memset(head, -1, sizeof head);
for (int i = 1; i <= m; i++) {
int u = gin(), v = gin(), w = gin();
add(u, v, w);
if (w >= 0)
add(v, u, w);
}
spfa();
if (t)
printf("YE5\n");
else
printf("N0\n");
}
return 0;
}
floyd算法
这个求的是多源最短路，也就是任意x到y的最短路径
使用了非常朴素的dp思想，令dp[i][j]表示从i到j的最短路，那么这条最短路要么是直接从i走到j，要么就是从另一个点k绕路了。所以dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j])
#include <bits/stdc++.h>
using namespace std;
int a[10001][10001];
int n,m;
int main () {
scanf("%d %d" ,&n,&m);
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= n; j++) {
if(i == j) a[i][j] = 0;
else a[i][j] = 0x3f3f3f3f;
}
}
for(int i = 1;i <= m; i++) {
int x,y,z;
scanf("%d %d %d" ,&x,&y,&z);
a[x][y] = min(a[x][y],z);
a[y][x] = min(a[y][x],z);
}
for(int k = 1;k <= n; k++) {
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= n; j++) {
a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
}
}
}
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= n; j++) {
printf("%d " ,a[i][j]);
}
printf("\n");
}
return 0;
}
最值得注意的就是加边的地方，a[x][y] = min(a[x][y],z);
这样是为了防止有重复的边，比如第一次加了3，第二次样例又加了5，不取最小值直接赋值的话就出问题了
后记 memset
memset可以用来给数组中的元素统一赋值，他的原理是，二进制数可以用8位16进制数来表示，如果用memset赋值一个0x3f，他就会把8位16进制数都设置成3f3f3f3f，进行赋值，因此她不能用来赋值一些奇怪的不规律的数值，例如INT_MAX，这一点一定要注意！
标签：nxt,head,Day9,int,cnt,寒假,judge,集训,dis From： https://www.cnblogs.com/Crazyman-W/p/17984678