一点模板

目录


树的直径

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100005;

struct EDGE {
    int to, le;
};
vector<EDGE> grp[MAXN];
int n, m, t, ans;
int f1[MAXN], f2[MAXN];

void add(int x, int y, int z) {
    grp[x].push_back((EDGE) {y, z});
}

void dp(int pos, int fa) {
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(grp[pos][i].to == fa) continue;
        dp(grp[pos][i].to, pos);
        if(f1[pos] < f1[grp[pos][i].to] + grp[pos][i].le) {
            f2[pos] = f1[pos];
            f1[pos] = f1[grp[pos][i].to] + grp[pos][i].le;
        }
        else if(f2[pos] < f1[grp[pos][i].to] + grp[pos][i].le) f2[pos] = f1[grp[pos][i].to] + grp[pos][i].le;
        ans = max(ans, f1[pos] + f2[pos]);
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int arg1, arg2;
        scanf("%d%d", &arg1, &arg2);
        add(arg1, arg2, 1);
        add(arg2, arg1, 1);
    }
    dp(1, 0);
    printf("%d", ans);
    return 0;
}

例题 树的直径

PBP0002Image

Sample In

10
1 2
1 3
2 4
4 5
4 6
1 7
5 8
7 9
7 10

Sample Out

6

RMQ问题的ST算法

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 1e5 + 5;

int n, m;
int lg[MAXN], rmq[MAXN][21], a[MAXN];
void init() {
    lg[0] = -1;
    for(int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; ++i) rmq[i][0] = a[i];
    for(int j = 1; (1 << j) <= n; ++j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++i)
            rmq[i][j] = max(rmq[i][j-1], rmq[i + (1 << j - 1)][j - 1]);
}

int getres(int l, int r) {
    int k = lg[r - l + 1];
    return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    init();
    for(int i = 1; i <= m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        printf("%d\n", getres(arg1, arg2));
    }
    return 0;
}

例题 「一本通 4.2 例 1」数列区间最大值

PBP0001Image

Sample In

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

Sample Out

5
8

Tarjan强连通分量

#include<stack>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN = 5e3 + 5;

vector<int> grp[MAXN];
stack<int> sta;
int n, m, _time = 1;
int vst[MAXN], low[MAXN];
bool insta[MAXN];
void dfs(int pos) {
    vst[pos] = low[pos] = _time++;
    sta.push(pos);
    insta[pos] = true;
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(!vst[grp[pos][i]]) {
            dfs(grp[pos][i]);
            low[pos] = min(low[pos], low[grp[pos][i]]);
        }
        else if(insta[pos]) low[pos] = min(low[pos], low[grp[pos][i]]);
    }
    if(vst[pos] == low[pos]) {
        int las;
        do {
            printf("%d ", sta.top());
            las = sta.top();
            sta.pop();
        } while(las != pos);
        printf("\n");
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        arg1–;
        arg2–;
        grp[arg1].push_back(arg2);
    }
    for(int i = 0; i < n; ++i) if(!vst[i]) dfs(i);
    return 0;
}

TarjanSample

Sample In

7 9
1 2
1 6
6 7
7 1
2 3
3 4
3 5
5 2
5 4

Sample Out

3
4 2 1
6 5 0

Tarjan缩点

#include<stack>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN = 1e5 + 5;

vector<int> grp[MAXN];
stack<int> sta;
int n, m, _time = 1, tmp, ans;
int vst[MAXN], low[MAXN];
int color[MAXN], totC, du[MAXN], cnt[MAXN];
bool insta[MAXN];
void dfs(int pos) {
    vst[pos] = low[pos] = _time++;
    sta.push(pos);
    insta[pos] = true;
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(!vst[grp[pos][i]]) {
            dfs(grp[pos][i]);
            low[pos] = min(low[pos], low[grp[pos][i]]);
        }
        else if(insta[pos]) low[pos] = min(low[pos], low[grp[pos][i]]);
    }
    if(vst[pos] == low[pos]) {
        int las;
        totC++;
        do {
            //printf("%d ", sta.top());
            color[sta.top()] = totC;
            las = sta.top();
            sta.pop();
        } while(las != pos);
        //printf("\n");
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        arg1–;
        arg2–;
        grp[arg1].push_back(arg2);
    }
    for(int i = 0; i < n; ++i) if(!vst[i]) dfs(i);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < grp[i].size(); ++j) {
            if(color[grp[i][j]] != color[i]) du[color[i]]++;
        }
        cnt[color[i]]++;
    }
    for(int i = 1;i <= totC; ++i) {
        if(du[i] == 0) {
            tmp++;
            ans = cnt[i];
        }
    }
    if(tmp == 0) printf("0\n");
    else if(tmp > 1) printf("0\n");
    else printf("%d\n", ans);
    return 0;
}

例题 Luogu P2341 [USACO03FALL]受欢迎的牛

Sample In

3 3
1 2
2 1
2 3

Sample Out

1

Tarjan割点与桥

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN = 5e3 + 5;

vector<int> grp[MAXN];
int n, m, _time = 1, ans, ans2;
int vst[MAXN], low[MAXN], fth[MAXN];
bool insta[MAXN], pts[MAXN];
bool brdg[MAXN][MAXN];
void dfs(int pos) {
    vst[pos] = low[pos] = _time++;
    int child = 0;
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(!vst[grp[pos][i]]) {
            child++;
            fth[grp[pos][i]] = pos;
            dfs(grp[pos][i]);
            if(fth[pos] == -1 && child >= 2) pts[pos] = true;
            if(fth[pos] != -1 && low[grp[pos][i]] >= vst[pos]) pts[pos] = true;
            if(low[grp[pos][i]] > vst[pos]) brdg[pos][grp[pos][i]] = true;
            low[pos] = min(low[pos], low[grp[pos][i]]);
        }
        else if(grp[pos][i] != fth[pos]) low[pos] = min(low[pos], low[grp[pos][i]]);
    }
}
int main() {
    memset(fth, -1, sizeof(fth));
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        arg1–;
        arg2–;
        grp[arg2].push_back(arg1);
        grp[arg1].push_back(arg2);
    }
    for(int i = 0; i < n; ++i) if(!vst[i]) dfs(i);
    for(int i = 0; i < n; ++i) if(pts[i]) ans++;
    for(int i = 0; i < n; ++i)
        for(int j = 0;j < n; ++j)
            if(brdg[i][j]) ans2++;
    printf("%d\n%d", ans, ans2);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注