您當前位置：首頁 > php開源 > php教程 > bzoj 1023 仙人掌圖

bzoj 1023 仙人掌圖

來源：程序員人生發布時間：2015-03-10 08:29:06 閱讀次數：3168次

Description

求1個神仙掌圖的直徑

Solution

神仙掌圖有個性質，1條邊要末是割邊要末就是在環內，那末我們可以對它進行Dp辣！

令 $f[u]表示以u為根的子樹最長鏈長度$

如果 $u-v$ 是橋的話轉移就是 $ans=max(ans,f[u]+f[v]+1)，f[u] = max(f[u], f[v]+1)$ ，由于當前f[u]都是由它的孩子更新來的

如果是環的話，變環為鏈，用單調隊列dp出ans,然后用環上的f值更新f[u]的值就能夠了，具體實現見代碼

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = N << 1;
int ans, ind, tot, cnt, fa[N], cir[N << 1], to[M << 1], nxt[M << 1], head[N], dfn[N], low[N], f[N];
inline int read(int &t) {
    int f = 1;char c;
    while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -1;
    t = c - '0';
    while (c = getchar(), c >= '0' && c <= '9') t = t * 10 + c - '0';
    t *= f;
}
struct data {
    int p, w;
}q[N];
void add(int u, int v) {
    to[tot] = v, nxt[tot] = head[u], head[u] = tot++;
    to[tot] = u, nxt[tot] = head[v], head[v] = tot++;
}
void gao() {
    int h = 1, r = 1;
    for (int i = 1; i <= cnt; ++i)  cir[cnt + i] = cir[i];
    for (int i = 1; i <= (cnt << 1); ++i) {
        while (h < r && i - q[h].p > cnt / 2)   ++h;
        while (h < r && q[r].w <= f[cir[i]] - i) --r;
        q[++r].p = i, q[r].w = f[cir[i]] - i;
        ans = max(ans, f[cir[i]] + i + q[h].w);
    }
}
void dfs(int u) {
    low[u] = dfn[u] = ++ind;
    for (int i = head[u], v; ~i; i = nxt[i]) {
        v = to[i];
        if (fa[v] != 0 && v != fa[u])   low[u] = min(low[u], dfn[v]);
        if (fa[v] == 0) {
            fa[v] = u;
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
    }
    for (int i = head[u], v; ~i; i = nxt[i]) {
        v = to[i];
        if (fa[v] == u && low[v] > dfn[u]) {    //bridge
            ans = max(ans, f[u] + f[v] + 1);
            f[u] = max(f[u], f[v] + 1);
        }
        if (fa[v] != u && dfn[u] < dfn[v]) { //circle
            cnt = 0;
            while (v != fa[u])  cir[++cnt] = v, v = fa[v];
            gao();
            for (int j = 1; j < cnt; ++j)   f[u] = max(f[u], f[cir[j]] + min(j, cnt - j));
        }
    }
}
int main() {
    int n, m;
    memset(head, -1, sizeof(head));
    read(n), read(m);
    for (int i = 1, x, y, z; i <= m; ++i) {
        read(x), read(y);
        for (int j = 1; j < x; ++j) {
            read(z);
            add(y, z);
            y = z;
        }
    }
    fa[1] = -1;
    dfs(1);
    printf("%d
", ans);
    return 0;
}