图

最短路径

堆优化版dij

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;

int N,M,a,b,c;
int h[maxn],e[maxn],w[maxn],ne[maxn],idx;//头节点表，编号表，权值表，链表
bool vis[maxn];int dis[maxn];//访问标记数组，距离数组
priority_queue<pii,vector<pii>,greater<pii> > heap;//堆，用堆去找目前距离最短的点(未访问过)

void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

int Dijkstra(){
    memset(dis,0x3f,sizeof dis);
    heap.push({0,1});//第一个是距离，第二个是编号
    dis[1] = 0;

    while(heap.size()){ 
        auto p = heap.top();heap.pop(); //找距离距离最短的点
        int d = p.first,s = p.second;
        if(vis[s]) continue;//如果已经访问过
        vis[s] = true;
        for(int i = h[s];i != -1;i = ne[i]){// i为地址
            int j = e[i]; //j是编号
            if(d+w[i] < dis[j]){
                dis[j] = d+w[i];
                heap.push({dis[j],j});
            }
        }
    }
    if(dis[N] == 0x3f3f3f3f) return -1;
    return dis[N];
}

树相关

求树的重心

无向图
树的重心的定义：
树若以某点为根，使得该树最大子树的结点数最小，那么这个点则为该树的重心，一棵树可能有多个重心。

树的重心的性质：
1、树上所有的点到树的重心的距离之和是最短的，如果有多个重心，那么总距离相等。

2、插入或删除一个点，树的重心的位置最多移动一个单位。

3、若添加一条边连接2棵树，那么新树的重心一定在原来两棵树的重心的路径上。

vector<int> adj[maxn];
int w[maxn]; //每个节点的权值
int sz[maxn]; //sz[u]：以u为根结点的树的权值和
int N,total;//N:总结点数，total：所有节点权值之和
int max_block = 2e9,H;//最大块的size，重心

int initsz(int u,int fa = -1){
    int sum = 0;
    for(auto v:adj[u]){
        if(v == fa) continue;
        sum += initsz(v,u);
    }
    return sz[u] = sum + w[u];
}

void findH(int u,int fa = -1){
    int mx = total-sz[u];
    for(auto v:adj[u]){
        if(v == fa) continue;
        mx = max(mx,sz[v]);
        findH(v,u);
    }
    if(mx < max_block){
        max_block = mx;
        H = u;
    }
}

求树的中心

基于树形dp
请你在树中找到一个点，使得该点到树中其他结点的最远距离最近，找到的这个点就是树的中心

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e4+10;
const int inf = 0x3f3f3f3f;

int N;
int h[maxn],e[maxn*2],w[maxn*2],ne[maxn*2],idx = 1;
int up[maxn],down1[maxn],down2[maxn],tag1[maxn];
//某个点，往上走的最远距离，往下走的最长距离，往下走的次长距离，往下走最长距离会经过的儿子结点编号
void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

int dfs_down(int u,int fa = -1){ //求每个结点往下走的最长和次长距离，以及最长经过的儿子编号
    int p1 = 0,p2 = 0;
    for(int i = h[u];i;i = ne[i]){
        int v = e[i],wei = w[i];
        if(v == fa) continue;
        int curp = dfs_down(v,u)+wei;
        if(curp > p1){
            p2 = p1,p1 = curp;
            tag1[u] = v;
        }else if(curp > p2){
            p2 = curp;
        }
    }
    down1[u] = p1,down2[u] = p2;//记录一下
    return p1;
}

void dfs_up(int u,int fa = -1){ //父结点更新子结点，找子结点向上的最大距离
    for(int i = h[u];i;i = ne[i]){
        int v = e[i],wei = w[i];
        if(v == fa) continue;
        if(tag1[u] == v){
            up[v] = wei + max(up[u],down2[u]);
        }else{
            up[v] = wei + max(up[u],down1[u]);
        }
        dfs_up(v,u);
    }
}

int main(){
    cin>>N;
    for(int i = 1;i<=N-1;i++){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs_down(1);
    dfs_up(1);
    int res = inf,H = -1;
    for(int i = 1;i<=N;i++) {
        int d = max(up[i], down1[i]); //向上、向下距离取最大值
        if (d < res) {
            res = d; //中心能移动的最大距离
            H = i;//树的中心
        }
    }

    return 0;
}

倍增法求LCA

无向图
一篇不错的LCA教程

int h[maxn],ne[maxn*2],e[maxn*2],idx = 1;
int q[maxn],fa[maxn][21],dep[maxn];
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void bfs(int root){
    int hh = 0,tt = -1;
    q[++tt] = root;
    dep[0] = 0,dep[root] = 1;

    while(hh<=tt){
        int u = q[hh++];
        for(int i = h[u];i;i = ne[i]){
            int v = e[i];
            if(dep[v]) continue;
            dep[v] = dep[u]+1;
            q[++tt] = v;
            fa[v][0] = u;
            for(int k = 1;k<=20;k++){
                fa[v][k] = fa[fa[v][k-1]][k-1];
            }
        }
    }
}

int LCA(int x,int y){
    if(dep[x] < dep[y]) swap(x,y);
    for(int k = 20;k>=0;k--){
        if(dep[fa[x][k]] >= dep[y])
            x = fa[x][k];
    }
    if(x == y) return x;
    for(int k = 20;k>=0;k--){
        if(fa[x][k] != fa[y][k]){
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}

求树的直径

无向图,可以有负边
基于树形dp

int N,d; // 结点数，直径
vector<pii> adj[maxn];
int dfs(int u = 1,int fa = -1){
    int p1 = 0,p2 = 0; //以u结点往下走的最长路径和次长路径
    for(auto p:adj[u]){
        int v = p.first,w = p.second;
        if(v == fa) continue;
        int curp  = max(0,dfs(v,u) + w); //如果是无权树，w = 1
        if(curp > p1) p2 = p1,p1 = curp;
        else if( curp > p2) p2 = curp;
    }
    d = max(d,p1 + p2);
    return p1;
}

图相关

染色法判断二分图

bool ok;
void DFS(int s){ 
    if(!ok) return ;
    for(int i = 0;i<h[s].size();i++){
        int j = h[s][i];
        if(col[j] == -1){
            col[j] = col[s]^1;//染和s结点相反的颜色
            DFS(j);
        }else if(col[j] == col[s]){ //如果已经和结点s颜色相同了，那么必定不是二分图
            ok = false;
            return;
        }
    }
}
memset(col,-1,sizeof col);//初始化染色标记数组
for(int i = 1;i<=N && ok;i++){ //对每个未染色点都进行DFS，因为可能有多个联通分量
    if(col[i] == -1){
        col[i] = 0; 
        DFS(i);
    }
}
然后是否ok