JZTXT

板子

发布时间 2023-09-30 17:19:16作者: 星影流灿

图论

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);
      }
    }
  }
}