526互联

noip Template (to be continued)

发布时间 2023-09-23 21:53:44作者: Razer_Mantis

\(noip\ Templates\)

\(Part 1 \ Graph\)

  1. Toposort
  2. Dijkstra
  3. SPFA
  4. Floyd
  5. Kruskal
  6. Prim
  7. Tarjan
  8. LCA

\(Graph\)

0. 链式前向星存图
int h[N], e[N], ne[N], idx; // 对于每个点k开一个单链表，存储所有可以走到的点。h[k]存储单链表头结点
// 添加一条边a->b
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
1. Toposort
bool toposort() {
  int hh = 0, tt = -1;
  for (int i = 1; i <= n; i++) if (!d[i]) q[++tt] = i; // d[i] 存储点i的入度
  while (hh <= tt) {
    int t = q[hh++];
    for (int i = h[t]; i != -1; i = ne[i]) {
      int j = e[i];
      if (--d[j] == 0) q[++tt] = j;
    }
  }
  return tt == n - 1; // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
}
2. Dijkstra
int n, h[N], w[N], e[N], ne[N], idx, dist[N]; // 邻接表存储所有边, dist[N]存储所有点到1号点距离
bool st[N]; // 存储每个点的最短距离是否已确定
int dijkstra() { // 求1号点到n号点的最短距离，如果不存在，则返回-1
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  priority_queue<PII, vector<PII>, greater<PII>> heap;
  heap.push({0, 1}); // first存储距离，second存储节点编号
  while (heap.size()) {
    auto t = heap.top();
    heap.pop();
    int ver = t.second, distance = t.first;
    if (st[ver]) continue;
    st[ver] = true;
    for (int i = h[ver]; i != -1; i = ne[i]) {
      int j = e[i];
      if (dist[j] > distance + w[i]) dist[j] = distance + w[i], heap.push({dist[j], j});
    }
  }
  if (dist[n] == 0x3f3f3f3f) return -1;
  return dist[n];
}
3. SPFA
int n, h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
int spfa() { // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
  memset(dist, 0x3f, sizeof dist);
  queue<int> q;
  q.push(1), st[1] = true, dist[1] = 0;
  while (q.size()) {
    auto t = q.front();
    q.pop(), st[t] = false;
    for (int i = h[t]; i != -1; i = ne[i]) {
      int j = e[i];
      if (dist[j] > dist[t] + w[i]) {
        dist[j] = dist[t] + w[i];
        if (!st[j]) q.push(j), st[j] = true; // 如果队列中已存在j，则不需要将j重复插入
      }
    }
  }
  if (dist[n] == 0x3f3f3f3f) return -1;
  return dist[n];
}

int n, h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
bool spfa() { // 如果存在负环，则返回true，否则返回false。不需要初始化dist数组, 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
  queue<int> q;
  for (int i = 1; i <= n; i++) q.push(i), st[i] = true;
  while (q.size()) {
    auto t = q.front();
    q.pop(), st[t] = false;
    for (int i = h[t]; i != -1; i = ne[i]) {
      int j = e[i];
      if (dist[j] > dist[t] + w[i]) {
        dist[j] = dist[t] + w[i], cnt[j] = cnt[t] + 1;
        if (cnt[j] >= n) return true; // 如果从1号点到x最短路中包含至少n个点（不包括自己），则存在环
        if (!st[j]) q.push(j), st[j] = true;
      }
    }
  }
  return false;
}
4. Floyd
void init() {
  for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= n; j ++ )
      d[i][j] = (i == j) ? 0 : INF;
}
void floyd() { // 算法结束后，d[a][b]表示a到b的最短距离
  for (int k = 1; k <= n; k ++ )
    for (int i = 1; i <= n; i ++ )
      for (int j = 1; j <= n; j ++ )
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
5. Kruskal
int n, m, p[N]; // n是点数，m是边数, p[N]是并查集的父节点数组
struct Edge { // 存储边
  int a, b, w;
  bool operator< (const Edge &W)const {return w < W.w;}
}edges[M];
int find(int x) { // 并查集核心操作
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}
int kruskal() {
  sort(edges, edges + m);
  for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
  int res = 0, cnt = 0;
  for (int i = 0; i < m; i ++ ) {
    int a = find(edges[i].a), b = find(edges[i].b), w = edges[i].w;
    if (a != b) p[a] = b, res += w, cnt++; // 如果两个连通块不连通，则将这两个连通块合并
  }
  if (cnt < n - 1) return INF;
  return res;
}
6. Prim
int n, g[N][N]; // n表示点数, g[N][N]邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
int prim() { // 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
  memset(dist, 0x3f, sizeof dist);
  int res = 0;
  for (int i = 0; i < n; i++) {
    int t = -1;
    for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
    if (i && dist[t] == INF) return INF;
    if (i) res += dist[t];
    st[t] = true;
    for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
  }
  return res;
}
7. Tarjan
int n, m, val[N], dfn[N], low[N], num, col[N], cnt, st[N], top;
// col记录每个点属于哪个联通分量, num记录遍历时间, cnt记录缩点完后有多少个点 
queue<int> q;
int new_val[N], du[N], f[N], ans;
vector<int> g[N], new_g[N];
void tarjan(int x) {
	dfn[x] = low[x] = ++num; st[++top] = x; //更新这个点 
	for (int i = 0; i < g[x].size(); i++) {
		int t = g[x][i];
		if (!dfn[t]) tarjan(t), low[x] = min(low[x], low[t]); // 往下更新（要确保下个点没被更新） 
		else if (!col[t])low[x] = min(low[x], dfn[t]); // 被更新了，但没被划分到强连通分量里 
	}
	if (dfn[x] == low[x])
    for (cnt++; st[top + 1] != x; top--)
    	col[st[top]] = cnt, new_val[cnt] += val[st[top]]; // 找到这个连通分量的代表，划分 
	// 为什么要有low?	因为我们最后要划分强连通分量（上面的操作），但不知道什么时候划分，所以添一个low。
	// 当dfn==low时就统计，这样不重不漏。
}
int main() {
	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); // 这个点仍不在任一个强连通分量里 
	// 目的：把每个点都放进一个强连通分量里，这样缩点完后就不存在环，就可以拓扑排序了
	// 所以流程就是：
	// 1.缩点,使整个图无环，方便后面拓扑排序  复杂度：O(n+m)
	// 2.拓扑排序找最大路径 复杂度：O(m)
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < g[i].size(); j++) {
			int t = g[i][j];
			if (col[i] != col[t]) new_g[col[i]].push_back(col[t]), du[col[t]]++; // 记录新图的边 
		}
}
8. LCA
int n, m, h[N], e[M], ne[M], idx, depth[N], fa[N][16], q[N];
void bfs(int root) {
  memset(depth, 0x3f, sizeof depth);
  int hh = 0, tt = 0;
  depth[0] = 0, depth[root] = 1, q[0] = root;
  while (hh <= tt) {
    int t = q[hh ++ ];
    for (int i = h[t]; ~i; i = ne[i]) {
      int j = e[i];
      if (depth[j] > depth[t] + 1) {
        depth[j] = depth[t] + 1, q[ ++ tt] = j, fa[j][0] = t;
        for (int k = 1; k <= 15; k++) fa[j][k] = fa[fa[j][k - 1]][k - 1];
      }
    }
  }
}
int lca(int a, int b) {
  if (depth[a] < depth[b]) swap(a, b);
  for (int k = 15; k >= 0; k--) if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
  if (a == b) return a;
  for (int k = 15; k >= 0; k--) if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
  return fa[a][0];
}