Tony.Lin 的小屋

~~11.29先补充到LCA，改天再说Orz~~
已补完

图的存储

直接存边

struct Edge
{
    int u, v;
} int n, m;

vector<Edge> e;
vector<bool> vis;

bool find_edge(int u, int v)
{
    for (int i = 1; i <= m; i++)
    {
        if (e[i].u == u && e[i].v)
        {
            return true;
        }
    }
    return false;
}

void dfs(int u)
{
    if (vis[u])
        return;
    vis[u] = true;
    for (int i = 1; i <= m; i++)
    {
        if (e[i].u == u)
        {
            dfs(e[i].v);
        }
    }
}

int main()
{
    cin >> n >> m;
    vis.resize(n + 1, false);
    e.resize(m + 1);
    for (int i = 1; i <= m; i++)
        cin >> e[i].u >> e[i].v;
    return 0;
}

邻接矩阵


int n, m;

vector<vector<bool>> adj;
vector<bool> vis;

bool find_edge(int u, int v)
{
    return adj[u][v];
}

void dfs(int u)
{
    if (vis[u])
        return;
    vis[u] = true;
    for (int v = 1; v <= n; v++)
    {
        if (adj[u][v])
            dfs(v);
    }
}

int main()
{
    cin >> n >> m;
    vis.resize(n + 1, false);
    adj.resize(n + 1, vector<bool>(n + 1, false));
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;
    }
    return 0;
}

邻接表


int n, m;
vector<vector<bool>> adj;
vector<bool> vis;

bool find_edge(int u, int v)
{
    for (int i = 0; i < adj[u].size(); i++)
    {
        if (adj[u][i] == v)
        {
            return true;
        }
    }
    return false;
}

void dfs(int u)
{
    if (vis[u])
        return;
    vis[u] = true;
    for (int i = 0; i < adj[u].size(); i++)
    {
        dfs(adj[u][i]);
    }
}

int main()
{
    cin >> n >> m;
    vis.resize(n + 1, false);
    adj.resize(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
return 0;
}

链式前向星

//head[u]和cnt初始值都为-1
void add(int u, int v)
{
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

//遍历u的出边
for (int i = head[u]; ~i; i = nxt[i])
{
    int v = to[i];
}

DFS

void dfs(int u)
{
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].x)
    {
        if (!vis[e[i].t])
        {
            dfs(v);
        }
    }
}

BFS

void bfs(int u)
{
    while (!Q.empty())
        Q.pop;
    Q.push(u);
    vis[u] = 1;
    d[u] = 0;
    p[u] = -1;
    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();
        for (int i = head[u]; i; i = e[i].x)
        {
            if (!vis[e[i].t])
            {
                Q.push(e[i].t);
                vis[e[i].t] = 1;
                d[e[i].t] = d[u] + 1;
                p[e[i].t] = u;
            }
        }
    }
}
void restore(int x)
{
    vector<int> res;
    for (int v = x; v = -1; v = p[v])
    {
        res.push_back(v);
    }
std:
    reverse(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++)
        printf("%d", res[i]);
    puts("");
}

树的直径

两次 DFS

第一次求任意一点的最远点，第二次求这个最远点的最远点，后两次节点连线即为直径

int n, c, d[N];
vector<int> E[N];
void dfs(int u, int fa)
{
    for (int v : E[u])
    {
        if (v == fa)
            continue;
        d[v] = d[u] + 1;
        if (d[v] > d[c])
            c = v;
        dfs(v, u);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1, 0);
    d[c] = 0;
    dfs(c, 0);
    cout << d[c] << '\n';
    return 0;
}

树形 DP

以1为树的根，每个节点作为子树的根向下，所能延伸的最大距离和次大距离之和

int n, d = 0;
int d1[N], d2[N];
vector<int> E[N];
void dfs(int u, int fa)
{
    d1[u] = d2[u] = 0;
    for (int v : E[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
        int t = d1[v] + 1;
        if (t > d1[u])
            d2[u] = d1[u], d1[u] = t;
        else if (t > d2[u])
            d2[u] = t;
    }
    d = max(d, d1[u] + d2[u]);
}
int main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1, 0);
    cout << d << '\n';
    return 0;
}

LCA

倍增

预处理fa(x,i)（表示x的第2^i个祖先）（用dfs）

将y次跳转优化为"y的二进制表示所含的1的个数"次跳转

vector<int> v[MXN];
vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

//lca初始化,接收起始节点和父亲节点
void dfs(int root, int fno)
{
    //初始化，2^0=1个祖先就是父亲节点，dep比父亲节点+1
    fa[root][0] = fno;
    dep[root] = dep[fa[root][0]] + 1;
    //初始化：其他的祖先节点：第2^i的祖先节点是第x^(n-1)个祖先节点的第2^(n-1)个祖先节点
    for (int i = 1; i < 31; i++)
    {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
        cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
    }
    //遍历子节点进行dfs
    int sz = v[root].size();
    for (int i = 0; i < sz; i++)
    {
        if (v[root][i] == fno)
            continue;
        cost[v[root][i]][0] = w[root][i];
        dfs(v[root][i], root);
    }
}

//lca，用倍增算法算取x和y的lca节点。
int lca(int x, int y)
{
    //令x比y深。
    if (dep[x] > dep[y])
        swap(x, y);
    //令y和x在一个深度。
    int tmp = dep[y] - dep[x], ans = 0;
    for (int j = 0; tmp; ++j, tmp >>= 1)
        if (tmp & 1)
            ans += cost[y][j], y = fa[y][j]
                               //如果这个时候y=x,那么x,y就都是他们自己的祖先。
                               if (y == x) return ans;
    //不然的话，找到第一个不是它们祖先的两个点。
    for (int j = 30; j >= 0 && y != x; --j)
    {
        if (fa[x][j] != fa[y][j])
        {
            ans += cost[x][j] + cost[y][j];
            x = fa[x][j];
            y = fa[y][j];
        }
    }
    //返回结果。
    ans += cost[x][0] + cost[y][0];
    return ans;
}

int main()
{
    //初始化表示祖先的数组fa，代价cost和深度dep。
    memset(fa, 0, sizeof(fa));
    memset(cost, 0, sizeof(cost));
    memset(dep, 0, sizeof(dep));
    //读入树：节点数总共n个。
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b >> c;
        a++, b++;
        v[a].push_back(b);
        v[b].push_back(a);
        w[a].push_back(c);
        w[b].push_back(c);
    }
    //为了计算lca而使用dfs。
    dfs(1, 0);
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        a++, b++;
        cout << lca(a, b) << endl;
    }
    return 0;
}

Tarjan

使用并查集记录某个结点的祖先结点。做法如下：

1.首先接受输入（邻接链表）、查询（存储在另一个邻接链表内）。查询边其实是虚拟加上去的边，为了方便，每次输入查询边的时候，将这个边及其反向边都加入到 queryEdge 数组里。
2.然后对其进行一次 DFS 遍历，同时使用 visited 数组进行记录某个结点是否被访问过、parent 记录当前结点的父亲结点。
3.其中涉及到了回溯思想，我们每次遍历到某个结点的时候，认为这个结点的根结点就是它本身。让以这个结点为根节点的 DFS 全部遍历完毕了以后，再将这个结点的根节点设置为这个结点的父一级结点。
4.回溯的时候，如果以该节点为起点，queryEdge 查询边的另一个结点也恰好访问过了，则直接更新查询边的 LCA 结果。
5.输出结果。

class Edge
{
public:
    int toVertex, fromVertex;
    int next;
    int LCA;
    Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1){};
    Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1){};
};

int head[MAX], queryHead[MAX];
Edge edge[MAX], queryEdge[MAX];
int parent[MAX], visited[MAX];
int vertexCount, edgeCount, queryCount;

void init()
{
    for (int i = 0; i <= vertexCount; i++)
    {
        parent[i] = i;
    }
}

int find()
{
    if (parent[x] == x)
    {
        return x;
    }
    else
    {
        return find(parent[x]);
    }
}
void tarjan(int u)
{
    parent[u] = u;
    visited[u] = 1;

    for (int i = head[u]; i != -1; i = edge[i].next)
        ;
    {
        Edge &e = edge[i];
        if (!visited[e.toVertex])
        {
            tarjan(e.toVertex);
            parent[e.toVertex] = u;
        }
    }

    for (int i = queryHead[u]; i != -1; i = queryEdge[i].next)
    {
        Edge &e = queryEdge[i];
        if (visited[e.toVertex])
        {
            queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
        }
    }
}
int main()
{
    memset(head, 0xff, sizeof(head));
    memset(queryHead, 0xff, sizeof(queryHead));
    cin >> vertexCount >> edgeCount >> queryCount;
    int count = 0;
    for (int i = 1; i < edgeCount; i++)
    {
        int start = 0, end = 0;
        cin >> start >> end;

        edge[count] = Edge(start, end, head[start]);
        head[start] = count;
        count++;
    }
    count = 0;
    for (int i = 0; i < queryCount; i++)
    {
        int start = 0, end = 0;
        cin >> start >> end;
        queryEdge[count] = Edge(start, end, head[start]);
        queryHead[start] = count;
        count++;
        queryEdge[count] = Edge(end, start, head[end]);
        queryHead[end] = count;
        count++;
    }
    init();
    tarjan(i);
    for (int i = 0; i < queryCount; i++)
    {
        Edge &e = queryEdge[i * 2];
        cout << e.LCA << endl;
    }
    return 0;
}

树的重心

定义：对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心

性质：
所有的子树大小都不超过整棵树大小的一半
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离

求法：
DFS计算每棵子树的大小，记录“向下”的子树的最大大小，利用总点数-当前子树（这里的子树指有根树的子树）的大小得到“向上”的子树的大小，然后就可以依据定义找到重心了。

//这份代码默认节点编号从1开始
int size[MAX],    //这个节点的大小（所有子树上的节点数+本节点
    weight[MAXN], //这个节点的重量
    centroid[2];  //用于记录树的重心（存的是节点编号
void GetCentroid(int cur, int fa)
{ //cur表示当前节点
    size[cur] = 1;
    weight[cur] = 0;
    for (int i = head[cur]; i != -1; i = e[i].nxt)
    {
        if (e[i].to != fa)
        { //e[i].to表示这个点通向的节点
            GetCentroid(e[i].to, cur);
            size[cur] += size[e[i].to];
            weight[cur] = max(weight[cur], size[e[i].to]);
        }
    }
    weight[cur] = max(weight[cur], n - size[cur]);
    if (weight[cur] <= n / 2)
    { //按照树的重心的定义统计
        centroid[centroid[0] != 0] = cur;
    }
}

拓扑排序

Kahn 算法

初始：集合S装所有入度0的点，L为空
每次S中取点u放入L，将u的所有边删除，若删除后有点入度为0，则放入S中
重复以上过程，直到S为空。检查图中有无边，若有则图为环路，否则返回L，其顺序即为拓扑排序的结果

fake code

bool toposort()
{
    q = new queue();
    for (int i = 0; i < n; i++)
        if (in_deg[i] == 0)
            q.push(i);
    ans = new vector();
    while (!q.empty())
    {
        u = q.pop();
        ans.push_back(u);
        for each
            edge(u, v)
            {
                if (--in_deg[v] == 0)
                    q.push(v);
            }
    }
    if (ans.size() == n)
    {
        for (int i = 1; i < n; i++)
            cout << ans[i] << endl;
        return true;
    }
    else
    {
        return false;
    }
}

DFS 算法

vector<int> G[MAXN] //邻接表
    int c[MAXN];    //标志数组
vector<int> topo;   //拓扑排序后的节点

bool dfs(int u)
{
    c[u] = -1;
    for (int v : G[u])
    {
        if (c[v] < 0)
            return false;
        else if (!c[v])
            if (!dfs(v))
                return false;
    }
    c[u] = 1;
    topo.push_back(u);
    return true;
}

bool toposort()
{
    topo.clear();
    memset(c, 0, sizeof(c));
    for (int u = 0; u < n; u++)
        if (!c[u])
            if (!dfs(u))
                return false;
    reverse(topo.begin(), topo.end());
    return true;
}

最短路

Floyd 算法

for (int k = 1; k <= n; k++)
{
    for (int x = 1; x <= n; x++)
    {
        for (int y = 1; y <= n; y++)
        {
            f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
        }
    }
}

Bellman-Ford 算法

松弛：dis(v)=min(dis(v),dis(u)+w(u,v))

此算法就是对每一条边进行松弛，直到没有可松弛的边

判负环：若第n次仍存在可松弛的边，则能抵达一个负环

struct edge
{
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn];
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++)
        {
            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 算法（队列优化

上一次被松弛的边，所连接的边才可能引起下一次操作，所以建一个队列维护“哪些节点会引起松弛操作”

判负环：最短路经过至少n条边

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

Warning:无负权边时最好用Dij

Dijkstra 算法

已确定最短路长度的点集为S，未确定的为T。初始化起点为0，其他点无穷大。
从T中选最短路长度最小的点放入S，对加入S的所有出边进行松弛操作，直到T为空。

struct edge
{
    int v, w;
};
struct node
{
    int dis, u;
    bool operator>(const node &a) const
    {
        return dis > a.dis;
    }
};
vector<edge> e[maxn];
int dis[maxn];
bool vis[maxn];
priority_queue<node, vector<node>, greater<node>> q;
void dijkstra(int n, int s)
{
    memset(dis, 63, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto ed : e[u])
        {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}