CF894E Ralph and Mushrooms_强连通分量_记忆化搜索

Code:
#include<cstdio>

#include<stack>

#include<cstring>

using namespace std;

const int maxn = 1000000 + 3;

stack<int>S;

int head[maxn], nex[maxn], val[maxn], to[maxn], cnt, n, m, s;

int low[maxn], dfn[maxn], vis[maxn], answer[maxn],  idx, scc;

long long quan[maxn];

inline void add_edge(int u, int v, int c)

{

    nex[++cnt] = head[u];

    head[u] = cnt;

    to[cnt] = v;

    val[cnt] = c;

}

void tarjan(int u)

{

    vis[u] = 1;

    S.push(u);

    low[u] = dfn[u] = ++scc;

    for(int v = head[u]; v ; v = nex[v])

    {

        if(!vis[to[v]])

        {

            tarjan(to[v]);

            low[u] = min(low[u], low[to[v]]);

        }

        else if(!answer[to[v]]) low[u] = min(low[u], dfn[to[v]]);

    }

    if(low[u] == dfn[u])

    {

        ++idx;

        for(;;)

        {

            int x = S.top(); S.pop();

            answer[x] = idx;

            if(x == u) break;

        }

    }

}

struct Math

{

    long long  sum[100097];

    long long C[100097];

    inline void init()

    {

        sum[0] = -1;

        for(int i = 2;i <= 100007; ++i) sum[i] = sum[i - 1] + i - 1;

        for(int i = 1;i <= 100007; ++i) C[i] = sum[i] + C[i - 1];              //第 (i + 1) 项的总和

    }

    inline long long get(int w)

    {

        int l = 1, r = 100000, ans = 0;

        while(l <= r)

        {

            int mid = (l + r) >> 1;

            if(sum[mid] <= w) ans = mid, l = mid + 1;

            else r = mid - 1;

        }

        return (long long) ans * w - C[ans];

    }

}M;

int head2[maxn], to2[maxn << 1], nex2[maxn << 1], cnt2, val2[maxn];

inline void add_edge2(int u,int v, int c)

{

    nex2[++cnt2] = head2[u];

    head2[u] = cnt2;

    to2[cnt2] = v;

    val2[cnt2] = c;

}

long long final[maxn];

long long dp(int u)

{

    if(final[u] != -1) return final[u];

    final[u] = quan[u];

    for(int v = head2[u]; v ; v = nex2[v])

    {

        final[u] = max(final[u], quan[u] + val2[v] + dp(to2[v]));

    }

    return final[u];

}

int main()

{

    scanf("%d%d",&n,&m);

    M.init();

    for(int i = 1;i <= m; ++i)

    {

        int a, b, c;

        scanf("%d%d%d",&a, &b, &c);

        add_edge(a, b, c);

    }

    scanf("%d",&s);

    for(int i = 1;i <= n; ++i)

    {

        if(!vis[i]) tarjan(i);

    }

    for(int i = 1;i <= n; ++i)

    {

        for(int v = head[i]; v ; v = nex[v])

        {

            if(answer[i] == answer[to[v]])

            {

                quan[answer[i]] += M.get(val[v]);

            }

            else

            {

                add_edge2(answer[i], answer[to[v]], val[v]);

            }

        }

    }

    memset(final, -1, sizeof(final));

    printf("%I64d",dp(answer[s]));

    return 0;

}
巴特西

CF894E Ralph and Mushrooms_强连通分量_记忆化搜索_缩点

最新文章

热门文章
