图论
Tarjan求强连通分量
int n, m, tot, top, cnt;
int dfn[N], low[N];
int q[N], ins[N], c[N];
vector<int> eg[N], scc[N], neg[N];
int cd[N];
void tarjan(int u){
dfn[u] = low[u] = ++tot;
q[++top] = u, ins[u] = 1;
for(auto x : eg[u]){
if(!dfn[x]){
tarjan(x);
low[u] = min(low[u], low[x]);
}
else if(ins[x]){
low[u] = min(low[u], dfn[x]);
}
}
if(dfn[u] == low[u]){
int e; cnt++;
do{
e = q[top--], ins[e] = 0;
c[e] = cnt, scc[cnt].push_back(e);
}while(u != e);
}
}
c[i]
表示第 i
个点的连通块编号, scc
储存每个连通块里的所有点
最短路
朴素Dijkstra
const int N = 505, M = 1e5 + 10;
int g[N][N], d[N], st[N];
int n, m;
int Dijkstra(){
memset(d, 0x3f, sizeof d);
d[1] = 0;
for(int i = 1;i <= n;i ++){
int tmp = 1e9, u;
for(int i = 1;i <= n;i ++)
if(!st[i] && tmp > d[i]) tmp = d[i], u = i;
st[u] = 1;
for(int i = 1;i <= n;i ++){
d[i] = min(d[i], d[u] + g[u][i]);
}
}
if(d[n] == 0x3f3f3f3f) return -1;
return d[n];
}
堆优化Dijkstra
const int N = 1e6;
typedef pair<int, int> PII;
int h[N], e[N], dist[N], st[N], w[N], ne[N], idx;
int n, m;
void add(int a, int b, int z){
e[idx] = b, ne[idx] = h[a], w[idx] = z, 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()){
PII tmp = heap.top();
heap.pop();
int u = tmp.second;
if(st[u]) continue;
st[u] = 1;
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(dist[j] > dist[u] + w[i]){
dist[j] = dist[u] + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Floyd
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
Bellman-Ford
struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn];
const int inf = 0x3f3f3f3f;
bool bellmanford(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0;
bool flag; // 判断一轮循环过程中是否发生松弛操作
for (int i = 1; i <= n; i++) {
flag = false;
for (int u = 1; u <= n; u++) {
if (dis[u] == inf) continue;
// 无穷大与常数加减仍然为无穷大
// 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = true;
}
}
}
// 没有可以松弛的边时就停止算法
if (!flag) break;
}
// 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
return flag;
}
SPFA
struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;
bool spfa(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0, vis[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1; // 记录最短路经过的边数
if (cnt[v] >= n) return false;
// 在不经过负环的情况下,最短路至多经过 n - 1 条边
// 因此如果经过了多于 n 条边,一定说明经过了负环
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return true;
}
拓扑排序
void topu_sort(){
queue<int> gs;
for(int i = 1; i <= cnt; i ++){
if(du[i] == 0){
gs.push(i);
}
}
while(gs.size()){
int t = gs.front(); gs.pop();
sx.push_back(t);
for(auto x : ng[t]){
du[x]--;
if(du[x] == 0){
gs.push(x);
}
}
}
}
标签:cnt,dist,int,板子,low,heap,dis
From: https://www.cnblogs.com/yduck/p/17738040.html