图论

图的存储

邻接矩阵

\(G[i][j]=1\) 表示有一条边从 \(i\) 到 \(j\)

邻接表

vector<int> es[MAXN];
/*
带权边
struct edge{ int to, w; };
vector<edge> es[MAXN];
*/

链式前向星

struct edge {
    int to, w, next;
}es[MAX_E];

int cnt = 0;

void init() {
    memset(head, -1, sizeof head);
}

void add_edge(int u, int v, int w) {   //加边
    es[cnt].to = v;
    es[cnt].w = w;
    es[cnt].next = head[u];
    head[u] = cnt++;
}
/*遍历
    for(int i = 1; i <= n; i++)
        for(int j = head[i]; i != -1; j = es[j].next)
*/

最短路

Bellman-Ford

单源最短路问题

\(O(VE)\) 支持负权

struct edge{ int from, to, w; };
edge es[MAX_E];

int d[MAX_V];
int V, E;

void BF(int s){
    memset(d, INF, sizeof d);
    d[s] = 0;
    for(int k = 0; k < V; k++){
        for(int i = 0; i < E; i++){
            edge e = es[i];
            if(d[e.from] != INF && d[e.to] > d[e.from]+e.w){
                d[e.to] = d[e.from]+w; //松弛操作
            }
        }
    }
}
//循环至多执行 V-1 次，一次松弛操作至少让确定的最短路+1，所以O(VE)，如果第 n 次任然更新了d，表示有负环
//把所有d[i]初始化为0，就可以找到所有的负圈
bool find_negative_loop(){
    memset(d, 0, sizeof d);
    for(int i = 0; i < V; i++){
        for(int j = 0; j < E; j++){
            edge e = es[j];
            if(d[e.to] > d[e.from]+e.w){
                d[e.to] = d[e.from]+e.w;
                if(i == V-1) return true;
            }
        }
    }
    return false;
}

Dijkstra

单源最短路问题

不支持负权边

检查存在 \(d[i][i]\) 为负数来判断是否有负环

\(O(ElogV)\) 用优先队列

typedef pair<int, int> P; 

vector<P> es[MAX_V];  //邻接表中first表示端点，second表示权值
int d[MAX_V];

void dijkstra(int s) {
    priority_queue< P, vector<P>, greater<P> > que; //队列中first表示最短路， second表示端点
    memset(d, INF, sizeof d);
    d[s] = 0;
    que.push(P(0, s));
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int u = p.second;
        if(d[u] < p.first) continue;
        for(int i = 0; i < es[u].size(); i++) {
            int v = es[u][i].first, w = es[u][i].second;
            if(d[v] > d[u]+w) { //松弛操作
                d[v] = d[u]+w;
                que.push(P(d[v], v));
            }
        }
    }
}

Floyd-Warshall

\(O(V^3)\)

dp:状态转移方方程 \(d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][i])\), 即 \(d[i][j] = min(d[i][j], d[i][k]+d[k][j])\)

int d[MAX_V[MAX_V];
void floyd() {
    for(int k = 0; k < V; k++)
        for(int i = 0; i < V; i++)
            for(int j = 0; j < V; j++)
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}   

路径还原

在松弛操作时记录每个结点的前趋结点\(path[i]\)即可, 查询时从后往前遍历

次短路

//每次更新最短路时看看被抛弃的值能不能更新次短路
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f;

vector<P> es[max_v];

int n, r, a, b, c;
int d1[max_v], d2[max_v]; //d2 次短路

void dijkstra(int s){
    memset(d1, inf, sizeof d1);
    memset(d2, inf, sizeof d2);
    priority_queue< P, vector<P>, greater<P> > que;

    d1[s] = 0;
    que.push(P(0, s));
    while(!que.empty()){
        P p = que.top(); que.pop();
        int u = p.second;
        if(d2[u] < p.first) continue;

        for(int i = 0; i < es[u].size(); i++){
            int v = es[u][i].first, w = es[u][i].second;
            int tmp = p.first+w;
            if(d1[v] > tmp){
                swap(tmp, d1[v]);
                que.push(P(d1[v], v));
            }
            if(tmp < d2[v] && tmp > d1[v]){
                d2[v] = tmp;
                que.push(P(d2[v], v));
            }
        }
    }
}

最小生成树

前提：图是连通的

Prim

\(O(V^2)\)

vector<edge> es[max_v];
int dis[MAX_V];
bool vis[MAX_V];

int prime(){
    memset(dis, inf, sizeof dis);
    memset(vis, false, vis);
    dis[0] = 0; //s
    int res = 0;
    while(true){
        int v = -1, mn = inf;
        for(int i = 0; i < V; i++)
            if(!visited[i] && dis[i] < mn)
                mn = dis[i], v = i;        
        if(v == -1) break;
        vis[v] = true;
        res += mn;
        for(int i = 0; i < es[v].size(); i++){
            edge e = es[v][i];
            dis[e.to] = min(dis[e.to], e.w);
        }
    }
    return res;
}

Kruskal

按照边的权值从小到达，利用并查集判断是否会产出圈，不会就加入

\(O(ElogE)\) 排序的复杂度

struct edge{ int from, to, w; };
edge es[MAX_E];

bool cmp(edge a, edge b){ return a.w < b.w; }

int kruskal(){
    sort(es, es+E, cmp);
    init(MAX_V);  //并查集的初始化
    int res = 0;
    for(int i = 0; i < E; i++){
        edge e = es[i];
        if(!same(e.from, e.to)){
            unite(e.from, e.to);
            res += e.w;
        }
    }
    return res;
}

网络流

最大流 Dinic

struct edge{ int to, cap, rev; } //rev记录反向边在 es[to] 中的索引

vector<edge> es[max_v];  //邻接表
int level[max_v];        //分层图
int iter[max_v];         //弧优化，记录结点增广过哪些边了，下次就不增广了

void add_edge(int from, int to, int cap)  {//加边

    es[from].push_back(edge{to, cap, es[to].size()});
    es[to].push_back(edge{from, 0, es[from].size()-1});   
}

void bfs(int s) {//分层图
    memset(level, -1, sizeof level);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        int v = que.front(), que.pop();
        for(int i = 0; i < es[i].size(); i++){
            edge &e = es[v][i];
            if(e.cap > 0 && level[e.to] < 0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int cur, int t, int f) { //增广路
    if(cur == t) return f;
    for(int &i = iter[cur]; i < es[cur].size(); i++){
        edge &e = es[cur][i];
        if(e.cap > 0 && level[cur] < level[e.to]){
            int d = dfs(e.to, t, min(f, e.cap));
            if(d > 0) {
                e.cap -= d;
                es[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t){
    int flow = 0;
    while(1){
        bfs(s);
        if(level[t] < 0) return flow;
        memset(iter, 0, sizeof iter);
        int f;
        while(f = dfs(s, t, inf) > 0) flow += f;
    }
}

最小费用流

负权边，用 BF 算法

const int inf = 0x3f3f3f3f;
struct edge{int to, cap, cost, rev; }

vector<edge> es[max_v];
int dist[max_v];
int pree[max_e], prev[max_v];   //前导顶点的对应的边的索引

void add_edge(int from, int to, int cap, int cost){
    es[from].push_back(edge{to, cap, cost, es[to].size()});
    es[to].push_back(edge{from, 0, -cost, es[from].size()-1});
}

int min_cost_flow(int s, int t, int f) { //起点 终点 流量
    int res = 0;
    while(f > 0){
        memset(dist, inf, sizeof dist);
        dist[s] = 0;
        while(true)  
            bool update = false;
            for(int i = 0; i < V; i++) {
                if(dist[i] == inf) continue;
                for(int j = 0; j < es[i].size(); j++) {
                    edge &e = es[i][j];
                    if(e.cap > 0 && dist[e.to] > dist[e.from]+e.cost)  {
                        dist[to] = dist[from]+e.cost;
                        prev[e.to] = i;
                        pree[e.to] = j;
                        update = true;
                    }
                }
            }
            if(!update) break;
        }

        if(dist[t] == inf) return -1;
        //沿s到t的最短路尽量增广
        int d = f;
        for(int i = t; i != s; i = prev[i])
            d = min(d, es[prev[i]][pree[i]].cap);

        f -= d;
        res += d*dist[t];
        for(int i = t; i != s; i = prev[i]) {
            edge &e = es[prev[i][pree[i]]];
            e.cap -= d;
            es[i][e.rev].cap += d;
        }
    }
    return res;
}

二分图匹配

最大流

添加原点和汇点，计算最大流

//计算机处理任务
bool can[max_n][max_m]; // can[i][j] : 计算机 i 能处理任务 j

void MaxMatch(){
    //计算机对应的顶点：0 ~ n-1
    //任务对应的顶点：n ~ n+m-1
    int s = n+m, t = n+m+1;
    for(int i = 0; i < n; i++){
        add_edge(s, i, 1);
    }
    for(int i = 0; i < m; i++){
        add_edge(n+i, t, 1);
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            add_edge(i, n+j, 1);
    cout << max_flow(s, t) << endl;
}

匈牙利算法

\(O(VE)\)

bool vis[max_v];
int match[max_v];
vector<int> es[max_v];

void add_edge(int u, int v){
    es[u].push_back(v);
    es[v].push_back(u);
}

bool dfs(int cur){
    for(int i = 0; i < es[cur].size(); i++){
        int v = es[cur][i];
        if(vis[v]) continue;
        vis[v] = true;
        if(!match[v] || dfs(match[v])){
            match[v] = cur;
            match[cur] = v;
            return true;
        }
    }
    return false;
}

int MaxMatch(){
    int res = 0;
    for(int i = 1; i <= n; i++){  //寻找增广路径
        memset(vis, 0, sizeof vis);
        if(!match[i] && dfs(i)) res++;     
    }
    return res;
}

Hopcroft-Karp

\(O(E\sqrt{V})\)

HDU 2389

int match[max_v], dep[max_v];
vector<int> es[max_v];

bool bfs() {
    memset(dep, 0, sizeof dep);
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!match[i]) q.push(i);
    bool flag = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < es[u].size(); i++) {
            int v = es[u][i];
            if (dep[v]) continue;
            dep[v] = dep[u] + 1;
            if (!match[v]) flag = true;
            else dep[match[v]] = dep[v] + 1, q.push(match[v]);
        }
    }
    return flag;
}

bool dfs(int u) {
    for (int i = 0; i < es[u].size(); i++) {
        int v = es[u][i];
        if (dep[v] != dep[u] + 1) continue;
        dep[v] = 0;
        if (!match[v] || dfs(match[v])) {
            match[v] = u; match[u]  = v;
             return true;
        }
    }
    return false;
}

int MaxMatch() {
    int res = 0;
    while (bfs()) {
    for (int i = 1; i <= n; i++)
        if (!match[i] && dfs(i)) res++;
    }
    return res;
}

连通性相关

强连通分量分解

\(O(V+E)\)

两次DFS，第一遍后序遍历并给顶点标号，第二遍对反向图遍历

vector<int> G[max_v];
vector<int> rG[max_v];    //反向图
vector<int> vs;           //vertex sequence
bool vis[max_v];
int cmp[max_v];           //所属强连通图的拓扑序

void add_edge(int u, int v){
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int v){
    vis[v] = true;
    for(int i = 0; i < G[v].size(); i++)
        if(!vis[G[v][i]]) dfs(G[v][i]);
    vs.push_back(v);
}

void rdfs(int v, int k){
    vis[v] = true;
    cmp[v] = k;
    for(int i = 0; i < rG[v].size(); i++)
        if(!vis[rG[v][i]]) rdfs(rG[v][i], k);
}

int scc() { //strongly connected component
    memset(vis, false, sizeof vis);
    vs.clear();
    for(int v = 0; v < V; v++)
        if(!vis[v]) dfs(v);

    memset(vis, false, sizeof vis);
    int k = 0;
    for(int i = vs.size()-1; i >= 0; i--)
        if(!vis[vs[i]]) rdfs(vs[i], k++);
    return k;
}

连通分支个数

并查集

树上问题

最近公共祖先(LCA)

\(O(n)\)

vector<int> G[maxn_v];
int root, parent[max_v], depth[max_v];

void dfs(int v, int p, int d){
    parent[v] = p, depth[v] = d;
    for(int i = 0; i < G[v].size(); i++)
        if(G[v][i] != p) dfs(G[v][i], v, d+1);
}

void init(){
    dfs(root, -1, 0);
}

int lca(int u, int v){
    //先把u,v走到同一深度
    while(depth[u] > depth[v]) u = parent[u]; 
    while(depth[v] > depth[u]) v = parent[v];
    //一起向上走
    while(u != v){
        u = parent[u], v = parent[v];
    }
    return u;
}

基于二分搜索的算法

对于任意结点v，可以通过

parent2[v] = parent[parent[v]]

parent4[v] = parent2[parent2[v]]

...

得到其向上走 \(2^k\)​ 步到达的顶点

每次搜索的复杂度： \(O(logn)\)，预处理的复杂度：\(O(nlogn)\)

vector<int> G[max_v];
int root, parent[max_k][max_v], depth[max_v];

void dfs(int v, int p, int d){
    depth[v] = d, parent[v] = p;
    for(int i = 0; i < G[v].size(); i++)
        if(G[v][i] != p) dfs(G[v][i], v, d+1);
}

void init(int V){
    //预处理parent[0]和depth
    dfs(root, -1, 0);
    //预处理parent
    for(int k = 0; k+1 < max_k; k++)
        for(int i = 0; i < V; i++) { //parent[k][v] 表示从 v 结点向上走 2^k 次的结点， 超过根时记作-1
            if(parent[k][i] < 0) parent[k+1][i] = -1;
            else parent[k+1][i] = parent[k][parent[k][i]];
        }
}

int lca(int u, int v){
    //让u和v走到同一深度
    if(depth[u] > depth[v]) swap(u, v); //让v的深度深一些
    for(int k = 0; k < max_k; k++) {
        if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v]; 
    }
    if (u == v) return u;
    //二分搜索计算LCA
    for (int k = max_k-1; k >= 0; k--) {
        if (parent[k][v] != parent[k][u]) {  //如果超过了他们的LCA也一定是一样的,不一样一定还没到LCA
            v = parent[k][v], u = parent[k][u];
        }
    }
    return parnet[0][u]; //?这里好像不太对?//
}

点分治

洛谷 P3806 POJ 1741

其他

二分图相关结论

定义：

匹配：在G中两两没有公共点的边集合M

边覆盖：G中任意顶点都至少是F中某条边的端点的边集合F

独立集：在G中两两互不相连的顶点集合S

顶点覆盖：G中的任意边都至少有一个端点属于S的顶点集合S

结论：

• 对于无孤立点的图，|最大匹配|+|最小边覆盖| = |V|

• |最大独立集|+|最小顶点覆盖| = |V|

• 对于二分图，|最大匹配| = |最小顶点覆盖|

简单证明：最大匹配时是每一对匹配中，不可能2个点都连接着未匹配的点（不然的话就会有增广路径，最大匹配还可以更大),

所以2个点中最多一个点连接着未匹配的点，选择那个点作为最小定点覆盖即可

2-SAT

布尔方程的可满足性问题

合取范式： \((a\vee b\vee\dots)\wedge(c\vee d\vee\dots)\)

2-SAT问题：合取范式的每个子句的文字不超过2的布尔方程的可满足性问题

将每个 \(a\vee b\) 改写成 \((\urcorner a \Rightarrow b \wedge \urcorner b \Rightarrow a)\)，以 \(\Rightarrow\)​ 关系为边建有向图，利用强连通分量分解

• 如果存在 \(x\) 和 \(\urcorner x\) ​​存在同一个强连通分量，无解

• 否则，对于每个布尔变量 \(x\)，如果 \(x\) 所在的强连通分量的拓扑序在 \(\urcorner x\) 之后，\(x\)​​ 为true

因为拓扑序在前的强连通分量可能存在通路到达在后的，所以在后的一定为 true

DFS序

当前结点的 in 和 out 包含了子树的所有结点

int in[N], out[N], tot = 0;
void dfs(int x, int dep) {
    in[x] = ++tot;
    for (int i = 0; i < es[x].size(); i++) dfs(es[x][i], dep + 1);
    out[x] = tot;
}