首页 > 其他分享 >板子

板子

时间:2023-09-30 17:22:06浏览次数:28  
标签:cnt dist int 板子 low heap dis

图论

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

相关文章

  • 字符串哈希板子
    字符串哈希板子http://oj.daimayuan.top/course/7/problem/485单哈希#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;constintp=9999971,base=101;intn,m;chara[N],b[N];//字符串a,bintha[N],hb[N],c[N];//ha是a的哈希函数,hb是b的哈希......
  • CF70D Professor's task 题解 & 动态凸包板子
    CF70DProfessor'stask题解前言此篇题解用的是\(Andrew\),不想看这种做法的可以绕道。题意动态凸包板子题。维护动态凸包。两种操作,加一个点或查询一个点是否在凸包内。题解首先你得会静态二维凸包。维护二维凸包的方法挺多的,比如什么\(Andrew\)算法,\(Jarvis\)算法还......
  • 一点板子
    快读、关同步intread(){intf=1,x=0;charc=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}returnx*f;}ios::s......
  • 板子
    LCTstructLinkCutTree{structNode{intch[2];intfa;intrev_tag;//...};vector<Node>tree;map<pair<int,int>,bool>edge;voidinit(intn/*...*/){tree.resize(n......
  • 平衡树板子
    替罪羊#include<algorithm>#include<iostream>usingnamespacestd;constintMaxN=4e5+10;constdoubleeps=0.75;intd[MaxN],l[MaxN],r[MaxN],cnt[MaxN],sum[MaxN],sz[MaxN],a[MaxN],tot,n,root,len;voidupdate(intx){//更新......
  • 二分板子
    1.求最大值最小while(l<=r){  mid=(l+r)>>1;  if(check(mid))ans=mid,r=mid-1;    elsel=mid+1; }例题洛谷p3853路标设置code#include<bits/stdc++.h>usingnamespacestd;intl,n,k,a[100010],r,ll,mid,ans,cnt;boolcheck......
  • 计算几何の板子
    一精度处理\(eps\)和\(sgn\)constdoubleeps=1e-8;intsgn(doublex){//判断大小if(fabs(x)<eps)return0;elsereturnx<0?-1:1;}二点1点的初始化向量的表示形式上与点完全相同重载点运算符,支持向量的四种运算structPoint{doublex,y;Poi......
  • 常用板子
    树状数组点击查看代码intc[N];intask(intx){intres=0;for(;x;x-=x&-x)ans+=c[i];returnans;}voidadd(inti,intx){for(;x<=n;x+=x&-x)c[x]+=y;}intpre(intl,intr){returnask(r)-ask(l-1);}......
  • Arduino官方推出两款H747板子,Portenta H7和Portenta Carrier
    这几天的CES2020上,Arduino亮相两款新板子。PortentaH7原理图和引脚图:Arduino-PortentaH7-schematic-V1.0.pdfPinout-PortentaH7_v3.pdf软件方面:1、编程支持Arduinocode,Python和JavaScript。2、基于MbedOS的Arduino框架。3、原生支持MbedAPI。4、AI方面支持TensorFlowLit......
  • 数论板子
    exgcd点击查看代码__int128exgcd(__int128as,__int128bs,__int128&x,__int128&y){if(bs==0){x=1;y=0;returnas;}__int128ans=exgcd(bs,as%bs,y,x);y-=(as/bs)*x;returnans;}a&c&lucas点击查看代码......