선인장도

본질적으로는 여전히 나무형 dp이다.원방나무를 세우고 원점을 만났을 때 직접 구하고(나무형 dp와 같을 때), 원점을 중전점으로 만났을 때 원의 반대편에서 통과하는 것을 고려해야 한다(최단 경로의 원칙을 충족시켜야 한다).원래는 원의 점에 대한\(n^{2}\)의 일치로 과감하게 시간을 초과했습니다.그러나 (n ^ {2}\) 의 dp는 단조로운 대기열 최적화가 가능한 dp가 분명하지 않습니다.그래서 해결하기 어려운 문제에 부딪혔을 때 반드시 융통성 있게 생각해야 한다.디테일이 하나 있습니다. 원을 복사하면\(max\) 의 영향을 제거할 수 있고 dp는 매우 편리합니다.

#include 
using namespace std;
#define maxn 500000
int n, m, N, timer, ans;
int fa[maxn], dfn[maxn], low[maxn];
int f[maxn][2], id[maxn], S[maxn];
int tmp[maxn], q[maxn];
int F[maxn][2], SS[maxn];

struct edge
{
    int cnp, head[maxn], to[maxn], last[maxn], w[maxn];
    edge() { cnp = 1; }
    void add(int u, int v, int ww)
    {
        to[cnp] = v, last[cnp] = head[u], w[cnp] = ww, head[u] = cnp ++;
        to[cnp] = u, last[cnp] = head[v], w[cnp] = ww, head[v] = cnp ++;
    }
}E1, E2;
 
int read()
{
    int x = 0, k = 1;
    char c;
    c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

void Solve(int u, int v)
{
    ++ N; int ID = 0, pre = 1;
    for(int i = v; i != fa[u]; i = fa[i])
        S[i] = pre ++, id[i] = ++ ID;
    S[N] = S[u], S[u] = 0;
    for(int i = v; i != fa[u]; i = fa[i])
        E2.add(N, i, min(S[i], S[N] - S[i]));
}

void Tarjan(int u)
{
    dfn[u] = low[u] = ++ timer; 
    for(int i = E1.head[u]; i; i = E1.last[i])
    {
        int v = E1.to[i];
        if(v == fa[u]) continue;
        if(!dfn[v])
        {
            fa[v] = u; Tarjan(v);
            low[u] = min(low[u], low[v]); 
        }
        else low[u] = min(low[u], dfn[v]);
        if(low[v] > dfn[u]) E2.add(u, v, 1);
    }
    for(int i = E1.head[u]; i; i = E1.last[i])
    {
        int v = E1.to[i]; 
        if(dfn[u] < dfn[v] && fa[v] != u) Solve(u, v);
    }
}

void update(int u, int w)
{
    if(w <= f[u][1]) return;
    if(w < f[u][0]) f[u][1] = w;
    else f[u][1] = f[u][0], f[u][0] = w; 
}

bool cmp(int a, int b) { return id[a] < id[b]; }

int Work(int u)
{
    int head = 1, tail = 1, cnt = 1, ans = 0, len = 0;
    for(int i = E2.head[u]; i; i = E2.last[i])
        tmp[++ cnt] = f[E2.to[i]][0], len ++;
    for(int i = 1; i <= len; ++ i)
        tmp[++ cnt] = tmp[i]; 
    q[head] = 1;
    for(int i = 2; i <= cnt; ++ i)
    {
        while(head < tail && i - q[head] > len / 2) ++ head;
        ans = max(ans, tmp[i] + tmp[q[head]] + i - q[head]);
        while(head <= tail && tmp[i] - i > tmp[q[tail]] - q[tail] ) -- tail;
        q[++ tail] = i;
    }
    return ans;
}

void dfs(int u, int ff)
{
    for(int i = E2.head[u]; i; i = E2.last[i])
    {
        int v = E2.to[i]; 
        if(v == ff) continue; else dfs(v, u); 
        update(u, f[v][0] + E2.w[i]);
    }
    if(u <= n) ans = max(ans, f[u][1] + f[u][0]);
    else ans = max(ans, Work(u)); 
}

int main()
{
    N = n = read(), m = read();
    for(int i = 1; i <= m; i ++)
    {
        int tot = read(), u, pre;
        for(int j = 1; j <= tot; j ++)
        {
            u = read(); if(j == 1) { pre = u; continue; }
            E1.add(u, pre, 1); pre = u;
        }
    }
    Tarjan(1);
    dfs(1, 0);
    printf("%d
", ans);
    return 0;
}

 
전재 대상:https://www.cnblogs.com/twilight-sx/p/9230863.html