树的一些性质

二叉树：第i层至多有2^(i-1)个节点，至少有1个；深度为k的二叉树至多有2^k-1个节点，至少有k个节点。

节点总数=边数(总度数)+1=二度点*2+一度点+1=二度点+一度点+叶子节点 推出 二度点+1=叶子节点个数

完全二叉树：n个结点的叶子节点个数有 n/2 向上取整个。深度为logn/log2+1。顺序存储时若1存根节点，则2n为左结点，2n+1为右结点。

二叉链表：n个结点共有2n个指针域，其中n-1个表示结构，n+1个空指针。利用起来这些空指针为线索二叉树。

先序/中序/后序线索二叉树：

LTag=0, lchild域指向左孩子; LTag=1, lchild域指向其前驱

RTag=0, rchild域指向右孩子; RTag=1, rchild域指向其后继

树的二叉链表表示法：左节点为子节点的第一个，可以不断找右节点找到此层的所有节点。

 

 

一，最短(长)路径

1.优先队列优化的Prim

贪心思想，维护到每个点最小距离，其中最小的必然在最短路径上。

int dis[MAXN];int T, n, m, c, tmp;struct Edge {    int to, nxt;    int cap;} edge[MAXN * 3];void addedge(int u, int v, int w) {    edge[tot].to = v;    edge[tot].cap = w;    edge[tot].nxt = head[u];    head[u] = tot++;}struct point { //到每个点的状态    int v, dis;    point(int a, int b) {        v = a, dis = b;    }    bool operator <(const point &tmp) const {        return dis > tmp.dis;    }};void dijkstra() {    priority_queue
     
       q;    for (int i = 1; i <= n; i++)        dis[i] = INF, vis[i] = 0; //vis表示是否已经确定最短路    dis[1] = 0;    while (!q.empty())        q.pop();    q.push(point(1, 0));    while (!q.empty()) {        point cur = q.top();        q.pop();        if (vis[cur.v])            continue;        vis[cur.v] = 1;        for (int i = head[cur.v]; i != -1; i = edge[i].nxt) {            int v = edge[i].to;            if (v == cur.v || vis[v])                continue;            if (dis[v] > dis[cur.v] + edge[i].cap) {                dis[v] = dis[cur.v] + edge[i].cap;                q.push(point(v, dis[v]));            }        }    }}
     

 

 

2.SPFA

动态规划的思想，用队列优化，每次只对更小的距离继续动规。

int dis[MAXN];bool vis[MAXN];int spfa() { // 求最长路    queue
     
       Q;    for (int i = low; i <= high; i++) {        dis[i] = -INF;        vis[i] = 0;    }    dis[low] = 0;    vis[low] = 1;    Q.push(low);    while (!Q.empty()) {        int u = Q.front();        Q.pop();        vis[u] = 0;        for (int i = head[u]; i != -1; i = edge[i].next) {            int v = edge[i].v;            if (dis[u] + edge[i].w > dis[v]) {                dis[v] = dis[u] + edge[i].w;                if (!vis[v]) {                    Q.push(v); //如果一个点入队超过点个数次，说明有负环                    vis[v] = 1;                }            }        }    }    return dis[high];}
     

 

 

3.floyd

int G[MAXN][MAXN], dis[MAXN][MAXN], pre[MAXN][MAXN];void floyd(int n) {    int i, j, k;    for (i = 0; i < n; i++)        for (j = 0; j < n; j++)            dis[i][j] = G[i][j], pre[i][j] = (i == j) ? -1 : i;    for (k = 0; k < n; k++)    for (i = 0; i < n; i++)    for (j = 0; j < n; j++)        if (dis[i][k] != INF && dis[k][j] != INF&& (dis[i][j] == INF || dis[i][k] + dis[k][j] < dis[i][j]))        dis[i][j] = dis[i][k] + dis[k][j], pre[i][j] = pre[k][j];}//不保存原图，不联通G为0void floyd(int n) {    int k, i, j;    //memcpy(NG, G, sizeof(G));    for (k = 1; k <= n; k++)    for (i = 1; i <= n; i++)    for (j = 1; j <= n; j++)        if (G[i][k] && G[k][j]&& (!G[i][j] || G[i][j] > G[i][k] + G[k][j]))            G[i][j] = G[i][k] + G[k][j];}

 

 

二，最小(大)生成树/最小(大)生成森林

1.优先队列优化Prim

int Prim(int n) {    priority_queue
     
       Q;    bool vis[MAXN];    memset(vis, 0, sizeof(vis));    vector
      
        vSelected;    int nDoneNum = 0;    int tot_w = 0;    Q.push(Edge(0, 0));    while (nDoneNum < n && !Q.empty()) {        Edge Min = Q.top();        Q.pop();        if (vis[Min.to])            continue;        tot_w += Min.w;        vis[Min.to] = 1;        nDoneNum++;        vSelected.push_back(Min.to);        for (int i = head[Min.to]; i != -1; i = edge[i].nxt) {            int v = edge[i].to;            if (v == Min.to || vis[v])                continue;            Q.push(edge[i]);        }    }    if (nDoneNum < n)        return -1; //图不连通    return tot_w;}
      
     

2.kruskal 最小(大)生成森林 每个联通块都保持联通性..并且总花费最小

int p[MAXN];void Init_Set() {    for (int i = 0; i <= MAXN; i++) {        p[i] = i;    }}int find(int x) {    if (x != p[x])        p[x] = find(p[x]);    return p[x];}int kruscal(int n) {    int x, y;    int edgeNum = 0;    int tot_w = 0;    Init_Set();    sort(edge, edge + tot);    for (int i = 0; i < tot; i++) {        x = find(edge[i].from);        y = find(edge[i].to);        if (x != y) {            edgeNum++;            p[x] = y;            tot_w += edge[i].w;        }    }    return tot_w;}

 

三，最短路和生成树的变化

1.次短路（维护个数） POJ3463

struct point {    int v, dis;    point(int a, int b) {        v = a, dis = b;    }    bool operator <(const point &tmp) const {        return dis > tmp.dis;    }};void dijkstra(int s) {    priority_queue
     
       q;    for (int i = 0; i <= n; i++) {        dis[i] = dis2[i] = INF;        cnt[i][0] = cnt[i][1] = vis[i][0] = vis[i][1] = 0;    }    dis[s] = 0;    q.push(point(s, 0));    cnt[s][0] = 1;    while (!q.empty()) {        point cur = q.top();        q.pop();        if (vis[cur.v][0] && vis[cur.v][1]) {            continue;        }        int p;        if (!vis[cur.v][0])            vis[cur.v][0] = 1, p = 0;        else            vis[cur.v][1] = 1, p = 1;        int Min_d = cur.dis;        for (int i = head[cur.v]; i != -1; i = edge[i].nxt) {            int v = edge[i].to;            if (v == cur.v)                continue;            if (dis[v] > Min_d + edge[i].cap) {                dis2[v] = dis[v];                cnt[v][1] = cnt[v][0];                dis[v] = Min_d + edge[i].cap;                cnt[v][0] = cnt[cur.v][p];                q.push(point(v, dis[v]));            } else if (dis[v] == Min_d + edge[i].cap) {                cnt[v][0] += cnt[cur.v][p];//                q.push(point(v, dis[v])); WA点            } else if (dis2[v] > Min_d + edge[i].cap) {                dis2[v] = Min_d + edge[i].cap;                cnt[v][1] = cnt[cur.v][p];                q.push(point(v, dis2[v]));            } else if (dis2[v] == Min_d + edge[i].cap) {                cnt[v][1] += cnt[cur.v][p];//                q.push(point(v, dis2[v])); WA点            }        }    }}
     

 

2.第K短路

建图时建一个反向图，从终点求到每个点的最短路作为AStar的估值。

#define MAXN 1009#define INF 0x3fffffffint head[MAXN], head2[MAXN];bool vis[MAXN];int cnt[MAXN];int tot, tot2;int n, m;struct Statement {    int v, d, h;};bool operator <(const Statement &a, const Statement &b) {    return a.d + a.h > b.d + b.h;}int dis[MAXN];struct Edge {    int to, nxt;    int cap;} edge[300003], edge2[300003];void init() {    tot = 0;    memset(head, -1, sizeof(head));    tot2 = 0;    memset(head2, -1, sizeof(head));}void addedge(int u, int v, int cap) {    edge[tot].to = v;    edge[tot].cap = cap;    edge[tot].nxt = head[u];    head[u] = tot++;}void addedge2(int u, int v, int cap) {    edge2[tot2].to = v;    edge2[tot2].cap = cap;    edge2[tot2].nxt = head2[u];    head2[u] = tot2++;}struct point {    int v, dis;    point(int a, int b) {        v = a, dis = b;    }};bool operator <(const point &a, const point &b) {    return a.dis > b.dis;}void dijkstra(int t) { //反向图从终点做最短路    priority_queue
     
       q;    for (int i = 1; i <= n; i++)        dis[i] = INF, vis[i] = 0; //vis表示是否已经确定最短路    dis[t] = 0;    q.push(point(t, 0));    while (!q.empty()) {        point cur = q.top();        q.pop();        if (vis[cur.v])            continue;        vis[cur.v] = 1;        for (int i = head2[cur.v]; i != -1; i = edge2[i].nxt) {            int v = edge2[i].to;            if (v == cur.v || vis[v])                continue;            if (dis[v] > dis[cur.v] + edge[i].cap) {                dis[v] = dis[cur.v] + edge[i].cap;                q.push(point(v, dis[v]));            }        }    }}int Astar_Kth(int s, int t, int K) {    Statement cur, nxt;    priority_queue
      
        Q;    if(dis[s] == INF)        return -1;    memset(cnt, 0, sizeof(cnt));    cur.v = s;    cur.d = 0; //步数    cur.h = dis[s];    Q.push(cur);    while (!Q.empty()) {        cur = Q.top();        Q.pop();        cnt[cur.v]++;        if (cnt[cur.v] > K)            continue;        if (cnt[t] == K)            return cur.d; //终点弹出K次说明找到第K短的路径        for (int i = head[cur.v]; i != -1; i = edge[i].nxt) {            int v = edge[i].to;            nxt.d = cur.d + edge[i].cap;            nxt.v = v;            nxt.h = dis[v];            Q.push(nxt);        }    }    return -1;}int main() {    int u, v, w;    int s, t, k;    while (~scanf("%d%d", &n, &m)) {        init();        for (int i = 0; i < m; i++) {            scanf("%d%d%d", &u, &v, &w);            addedge(u, v, w);            addedge2(v, u, w);        }        scanf("%d%d%d", &s, &t, &k);        if (s == t)            k++;        dijkstra(t);        printf("%d\n", Astar_Kth(s, t, k));    }    return 0;}
      
     

3.次小生成树

//POJ 1679 求次小生成树权值和 首先求最小生成树T 然后从每个结点BFS遍历最小生成树T//更新二维数组Max_w[u][v]记录结点u到结点v的路劲上边的最大值(即最大边的值)//然后枚举不在T中的边(u,v)，计算T- Max_w[u][v] + w(u,v)的最小值，即为次小生成树的权值int n, m;int Max_w[101][101];int tot;int head[MAXN];void init() {    tot = 0;    memset(head, -1, sizeof(head));}struct Edge {    int from, to, nxt;    int w;    bool flag;    Edge() {        flag = 0;    }    Edge(int _to, int _w) :            to(_to), w(_w) {    }    bool operator <(const Edge & tmp) const {        return w < tmp.w; //换成
     <就是最大生成树 }} edge[250000];vector
       > SMT[MAXN];int kruscal() {    int x, y;    int edgeNum = 0;    int tot_w = 0;    Init_Set();    for (int i = 0; i <= n; i++)        SMT[i].clear();    sort(edge, edge + tot);    for (int i = 0; i < tot; i++) {        x = find(edge[i].from);        y = find(edge[i].to);        if (x != y) {            edgeNum++;            p[x] = y;            SMT[edge[i].from].push_back(make_pair(edge[i].to, edge[i].w));            SMT[edge[i].to].push_back(make_pair(edge[i].from, edge[i].w));            edge[i].flag = 1;            tot_w += edge[i].w;        }    }    return tot_w;}struct Node {    int to, Max;};void bfs(int root) {    bool vis[MAXN];    memset(vis, 0, sizeof(vis));    queue
      
        que;    Node now;    now.Max = 0;    now.to = root;    que.push(now);    vis[root] = 1;    while (!que.empty()) {        Node top = que.front();        que.pop();        for (size_t i = 0; i < SMT[top.to].size(); i++) {            now.to = SMT[top.to][i].first;            if (!vis[now.to] && now.to != top.to) {                now.Max = max(SMT[top.to][i].second, top.Max);                Max_w[root][now.to] = now.Max;                vis[now.to] = 1;                que.push(now);            }        }    }}void second_MST() {    int mst = kruscal();    for (int i = 1; i <= n; i++)        bfs(i);    int smst = INF;    for (int i = 0; i < m; i++) {        if (!edge[i].flag)            if (mst + edge[i].w - Max_w[edge[i].from][edge[i].to] < smst)                smst = mst + edge[i].w - Max_w[edge[i].from][edge[i].to];    }    if (smst == mst)        printf("Not Unique!\n");    else        printf("%d\n", mst);}
      
     

4.最小度生成树（有一个点的度不能超过K）

 

先不计这个点求最小生成森林，产生的联通块数量就是最小度数，在这个最小度数上增加，每次找一条不在生成树上和最小度点相连的那些边中，连上去掉成环环上最大边这个增加值最小的选择相连。通过dfs可以预处理出每个点被成环后环上的最大边，和次小生成树的方法一致。这里dfs即不能走到父节点，也不能走到最小度点，不然就死循环WA

#define MAXN 1009int head[MAXN], tot;int N, M, K;int ans;bool vis[MAXN];pair
     
       prim(int u) {    int Min_dis = 0x3fffffff, k = 0;    priority_queue
      
        Q;    Edge cur;    cur.u = u, cur.v = u, cur.w = 0;    Q.push(cur);    while (!Q.empty()) {        cur = Q.top();        Q.pop();        if (vis[cur.v])            continue;        vis[cur.v] = 1;        tree[cur.u][cur.v] = tree[cur.v][cur.u] = 1;        ans += cur.w;        for (int i = head[cur.v]; i != -1; i = edge[i].next)            if (edge[i].v == 0 && Min_dis > edge[i].w) {                Min_dis = edge[i].w, k = cur.v;                break;            }        for (int i = head[cur.v]; i != -1; i = edge[i].next) {            int v = edge[i].v;            if (v == cur.v || vis[v])                continue;            Q.push(edge[i]);        }    }    return make_pair(k, Min_dis);}struct DEL {    int u, v;    int dis;} del[MAXN];void dfs(int cur, int fa) {    for (int i = head[cur]; i != -1; i = edge[i].next) {        int v = edge[i].v;        if (v == 0 || v == fa || !tree[cur][v])            continue;        if (del[cur].dis < edge[i].w) {            del[v].dis = edge[i].w;            del[v].u = cur, del[v].v = v;        } else {            del[v] = del[cur];        }        dfs(v, cur);    }}void solve() {    memset(vis, 0, sizeof(vis));    memset(tree, 0, sizeof(tree));    memset(del, 0, sizeof(del));    vis[0] = 1;    for (int i = 1; i < N; i++) {        if (vis[i])            continue;        K--;        pair
       
         k = prim(i);        ans += k.second;        tree[k.first][0] = tree[0][k.first] = 1;        del[k.first].dis = k.second;        del[k.first].u = 0, del[k.first].v = k.first;        dfs(k.first, 0);    }    while (K--) {        int Min_add = 0x3fffffff, k;        for (int i = head[0]; i != -1; i = edge[i].next) {            int v = edge[i].v;            if (!tree[0][v]) {                if (Min_add > edge[i].w - del[v].dis)                    Min_add = edge[i].w - del[v].dis, k = v;            }        }        if (Min_add >= 0)            break;        ans += Min_add;        tree[0][k] = tree[k][0] = 1;        tree[del[k].u][del[k].v] = tree[del[k].v][del[k].u] = 0;        dfs(k, 0);    }}
       
      
     

 

 

5.走K条边的floyd最短距离 属于矩阵相乘的应用

#include
     
      #include
      
       #define N 101struct Matrix {    int edge[N][N];} map, tmp, res;int n, f[N * 10];Matrix mul(Matrix x, Matrix y) {    memset(tmp.edge, 0x3f3f3f3f, sizeof(tmp.edge));    int i, j, k;    for (i = 1; i <= n; i++)        for (j = 1; j <= n; j++)            for (k = 1; k <= n; k++)                if (tmp.edge[i][j] > x.edge[i][k] + y.edge[k][j])                    tmp.edge[i][j] = x.edge[i][k] + y.edge[k][j];    return tmp;}void quickpow(int k) {    memset(res.edge, 0x3f3f3f3f, sizeof(res.edge));    for (int i = 1; i <= n; i++)        res.edge[i][i] = 0;    while (k) {        if (k & 1)            res = mul(res, map);        map = mul(map, map);        k >>= 1;    }}int main() {//    freopen("data3.txt", "r", stdin);    int k, t, s, e, len, u, v;    scanf("%d%d%d%d", &k, &t, &s, &e);    memset(map.edge, 0x3f3f3f3f, sizeof(map.edge));    memset(f, -1, sizeof(f));    int num = 1;    for (int i = 0; i < t; i++) {        scanf("%d%d%d", &len, &u, &v);        if (f[u] == -1)    //离散化            f[u] = num++;        if (f[v] == -1)            f[v] = num++;        map.edge[f[u]][f[v]] = map.edge[f[v]][f[u]] = len;    }    n = num - 1;    quickpow(k);    printf("%d\n", res.edge[f[s]][f[e]]);    return 0;}
      
     

 

#define N 109#define INF 0x7fint n, m;int dis[N][N][N];int vis[N][N], tmp[N][N];void init() {    memset(vis, -1, sizeof(vis));    memset(dis, 0x7f, sizeof(dis));}void floyd_k() {    for (int k = 1; k <= n; k++)        for (int i = 1; i <= n; i++)            for (int j = 1; j <= n; j++)                if (vis[i][k] != -1 && vis[k][j] != -1) {                    if (vis[i][j] == -1)                        vis[i][j] = vis[i][k] + vis[k][j];                    else                        vis[i][j] = min(vis[i][j], vis[i][k] + vis[k][j]);                }    for (int k = 1; k <= n; k++) { // 走k条边        for (int i = 1; i <= n; i++)            for (int j = 1; j <= n; j++) {                for (int h = 1; h <= n; h++) {                    if (vis[i][h] == -1 || k < vis[i][h] || vis[h][j] == -1                            || k < vis[h][j])                        continue;                    dis[i][j][k] = min(dis[i][j][k],                            dis[i][h][k - 1] + dis[h][j][0]);                }            }    }}int main() {    while (~scanf("%d%d", &n, &m)) {        init();        for (int i = 0; i < m; i++) {            int u, v, w;            scanf("%d%d%d", &u, &v, &w);            dis[u][v][0] = w;            vis[u][v] = 1;        }        floyd_k();    }    return 0;}

 

四，最近公共祖先

1.离线

int indegree[MAX];int visit[MAX], father[MAX];vector
     
       tree[MAX],Qes[MAX]; //树，查询int ancestor[MAX];//记录公共祖先void init(int n){      for(int i=1;i<=n;i++){        father[i]=i;        indegree[i]=visit[i]=0;        tree[i].clear();        Qes[i].clear();    }}  void LCA(int u){    ancestor[u]=u;    for(int i=0;i
     

2.倍增

const int LOG = 20;struct node {    int to, val, next;} edge[MAXN];int dis[MAXN];int po[MAXN], tol;int dep[MAXN];int p[MAXN][22];void dfs(int x, int fa, int depth, int cost) {    dep[x] = depth;    p[x][0] = fa;    dis[x] = cost;    for (int i = 1; i <= LOG; i++)        p[x][i] = p[p[x][i - 1]][i - 1]; // 倍增，存的是节点x第2^i个祖先    for (int i = po[x]; i; i = edge[i].next) {        int y = edge[i].to;        if (y != fa)            dfs(y, x, depth + 1, cost + edge[i].val);    }}int lca(int x, int y) { // 倍增求lca    if (dep[x] > dep[y])        swap(x, y);    if (dep[x] < dep[y]) {        int del = dep[y] - dep[x];        for (int i = 1; i <= LOG; i++)            if (del >> i & 1)                y = p[y][i]; //将y与x深度调整为相同    }    if (x != y) {        for (int i = LOG - 1; i >= 0; i--)            if (p[x][i] != p[y][i]) {                x = p[x][i];                y = p[y][i];            }        x = p[x][0], y = p[y][0];    }    return x;}//根据x,y的最近公共祖先求x到y路径上第K个点int up(int x, int k) { // 求节点x的第k个祖先编号    for (int i = 0; i < LOG; i++)        if (k >> i && (k >> i & 1))            x = p[x][i];    return x;}int path_k(int k, int x, int y) { // 求x到y路径上第k节点编号    int ca = lca(x, y);    if (dep[x] - dep[ca] + 1 >= k) {        return up(x, k - 1);    } else {        k -= dep[x] - dep[ca];        k = dep[y] - dep[ca] + 1 - k;        return up(y, k);    }}

 

五，树链剖分

每个点（或者边）有权值

我们要做的就是询问两个点之间路径上各点（边）权值的最大、最小，权值和（就是线段树能干的）

然后我们还要支持在线更改任意节点（边）的权值。

我们要做的是轻重链剖分，首先我们看几个定义

size：和SBT里的一样，size[i]为以该点为根节点的子树一共有几个节点。

重儿子：一个节点当不为叶子节点的时候有且只有一个重儿子，重儿子为该点的儿子中size最大的，有多个最大时任选一个。

重链：由根节点开始，每个点每次都访问自己的重儿子，一直访问到叶子节点，就组成了一条重链

　　   那么对于一个点的非重儿子来说，以他为根节点，可以重新访问出一条重链。

　　   重链几个明显的性质就是互不重合且所有重链覆盖所有点，重链之间由一条不在重链上的边，我们称作轻边。

 

例图：红色的线画出的为重链，其中6号点自己为一条重链

 

siz[v]表示以v为根的子树的节点数，dep[v]表示v的深度(根深度为1)

top[v]表示v所在的链的顶端节点，fa[v]表示v的父亲

son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子）

w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置

struct Edge {    int to, next;} edge[MAXN * 2];int head[MAXN], tot;int top[MAXN]; //top[v]表示v所在的重链的顶端节点int fa[MAXN]; //父亲节点int deep[MAXN]; //深度int num[MAXN]; //num[v]表示以v为根的子树的节点数int p[MAXN]; //p[v]表示v与其父亲节点的连边在线段树中的位置int fp[MAXN]; //和p数组相反int son[MAXN]; //重儿子:子节点中num[]最大的节点int pos; //形成线段树区间长度void init() {    tot = 0;    memset(head, -1, sizeof(head));    pos = 0;    memset(son, -1, sizeof(son));}void addedge(int u, int v) {    edge[tot].to = v;    edge[tot].next = head[u];    head[u] = tot++;}void dfs(int u, int pre, int d) { //第一遍dfs求出fa,deep,num,son    deep[u] = d;    fa[u] = pre;    num[u] = 1;    for (int i = head[u]; i != -1; i = edge[i].next) {        int v = edge[i].to;        if (v != pre) {            dfs(v, u, d + 1);            num[u] += num[v];            if (son[u] == -1 || num[v] > num[son[u]])                son[u] = v;        }    }}void getpos(int u, int sp) { //第二遍dfs求出top和p    top[u] = sp;    p[u] = pos++;    fp[p[u]] = u;    if (son[u] == -1)        return;    getpos(son[u], sp); //先加入重边使重边在线段树中连续    for (int i = head[u]; i != -1; i = edge[i].next) {        int v = edge[i].to;        if (v != son[u] && v != fa[u]) //最后加入轻边            getpos(v, v);    }}//线段树RMQ最值struct Node {    int l, r;    int Max;} tree[MAXN * 4];void build(int num, int l, int r) {    tree[num].l = l;    tree[num].r = r;    tree[num].Max = 0;    if (l == r)        return;    int mid = (l + r) / 2;    build(num << 1, l, mid);    build((num << 1) | 1, mid + 1, r);}void push_up(int num) {    tree[num].Max = max(tree[num << 1].Max, tree[(num << 1) | 1].Max);}void update(int i, int k, int val) { // 更新线段树的第k个值为val    if (tree[i].l == k && tree[i].r == k) {        tree[i].Max = val;        return;    }    int mid = (tree[i].l + tree[i].r) / 2;    if (k <= mid)        update(i << 1, k, val);    else        update((i << 1) | 1, k, val);    push_up(i);}int query(int i, int l, int r) {    if (l <= tree[i].l && tree[i].r <= r)        return tree[i].Max;    int mx1 = -INF, mx2 = -INF;    int mid = (tree[i].l + tree[i].r) / 2;    if (l <= mid)        mx1 = query(i << 1, l, r);    if (r > mid)        mx2 = query(i << 1, l, r);    return max(mx1, mx2);}int find(int u, int v) { //查询u->v边的最大值    int f1 = top[u], f2 = top[v];    int tmp = -INF;    while (f1 != f2)  //u,v的LCA问题    {        if (deep[f1] < deep[f2]) {            swap(f1, f2);            swap(u, v);        }        tmp = max(tmp, query(1, p[f1], p[u]));  //u到top[u]区间最值        u = fa[f1];        f1 = top[u];  //迭代到top[u]的父节点    }    if (u == v)        return tmp;    if (deep[u] > deep[v])        swap(u, v);    return max(tmp, query(1, p[son[u]], p[v]));}int e[MAXN][3];  //树上边的始终点与边权int main() {    while (T--) {        init();        scanf("%d", &n);        for (int i = 0; i < n - 1; i++) {            scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);            addedge(e[i][0], e[i][1]);            addedge(e[i][1], e[i][0]);        }        dfs(1, 0, 0);        getpos(1, 1);        build(1, 0, pos - 1);        for (int i = 0; i < n - 1; i++) {            if (deep[e[i][0]] > deep[e[i][1]])                swap(e[i][0], e[i][1]);            update(1, p[e[i][1]], e[i][2]);        }        char op[10];        int u, v;        while (~scanf("%s", op)) {            if (op[0] == 'D')                break;            scanf("%d%d", &u, &v);            if (op[0] == 'Q')                printf("%d\n", find(u, v));            else                update(1, p[e[u - 1][1]], v);        }    }    return 0;}

 

六，强连通分量

1.有向图 

HDU 4635

int in[MAXN], out[MAXN];vector
     
       G[MAXN],NG[MAXN];//n个点图强连通分量缩点belong[],缩点的点集NG<>int dfn[MAXN],low[MAXN],belong[MAXN];int Count,n,m,cnt;bool instack[MAXN];stack 
      
       stap;void init(){    Count=cnt=0;    memset(dfn,0,sizeof(dfn));    memset(belong,0,sizeof(belong));    memset(instack,0,sizeof(instack));}void tarjan(int x){    int i;    dfn[x]=low[x]=++cnt;    stap.push(x);    instack[x]=1;    for(i=0;i
      
     

2.无向图

void Tarjan(int u,int father){    int i;    low[u] = dfn[u] = nTime ++;    stap.push(u);    instack[u]=true;    int cnt=0;    for( i = 0;i < G[u].size() ;i ++ ) {        int v = G[u][i];        if( ! dfn[v]) {            Tarjan(v,u);            low[u] = min(low[u],low[v]);        }        else if(father==v){  //反向边更新                        if(cnt)low[u]=min(low[u],dfn[v]);                       cnt++;                }                else low[u]=min(low[u],dfn[v]);    }    if(low[u]==dfn[u]){        count++;        while(1){            int tmp=stap.top();            stap.pop();            belong[tmp]=count;            instack[tmp]=false;            if(tmp==u) break;        }    }}void work(){    count=0;    memset(dfn,0,sizeof(dfn));    Tarjan(1,0);}

 

 

七，拓扑排序

对有向无环图进行拓扑排序，检测图中是否有环(注意，SPFA检测是负环)。

① AOV网(Activity  On Vertices)—用顶点表示活动的网络

② AOE网(Activity  On Edges)—用边表示活动的网络

对有先决条件的事件找到一个完成序列。

#define MAXN 100int mat[MAXN][MAXN];int ret[MAXN];int topsort(int n) {    int d[MAXN], i, j;    int cnt = 0;    for (i = 0; i < n; i++) //计算每个点的入度        for (d[i] = j = 0; j < n; d[i] += mat[j++][i])            ;    while (cnt < n) {        for (i = 0; d[i] && i < n; i++)            ;        if (i == n)            return 0; //说明有环        ret[cnt++] = i;        for (d[i] = -1, j = 0; j < n; j++) //和此点相连的入度减一            d[j] -= mat[i][j];    }    return cnt;}