noip模拟赛传球接力

【问题描述】
n 个小朋友在玩传球。小朋友们用 1 到 n 的正整数编号。每个小朋友有一个固定的传球
对象，第 i 个小朋友在接到球后会将球传给第 ai个小朋友，并且第 i 个小朋友与第 ai个小朋
友之间的距离为 di。
一次传球接力是这样进行的：由一个小朋友发球，将球传给他的传球对象，之后接到球
的小朋友再将球传给自己的传球对象，如此传球若干次后停止。期间，包括发球者在内，每
个小朋友至多只能拿到球一次。一次传球接力的总距离是每次传球的距离的总和。
小朋友们想进行一次总距离最长的传球接力，现在需要你帮助他们求出满足上述要求的
传球接力的最长总距离。
【输入】
输入的第 1 行包含 1 个整数 n。
接下来的 n 行，第 i 行包含两个整数 ai 和 di，意义如题目中所述，两个数间用一个空格
隔开。
【输出】
输出包含 1 个数，表示传球接力总距离的最大值。
【输入输出样例 1】

pass.in	pass.out
5 2 1 3 2 4 1 2 3 3 3	7

见选手目录下的 pass / pass1.in 与 pass / pass1.out
【输入输出样例 1 说明】
由第 5 个小朋友发球，传给第 3 个小朋友，再传给第 4 个小朋友，总距离为 3+1+3=7
【数据规模与约定】
对于 50%的数据， n≤1,000
对于 100%的数据， n≤500,000， 1≤ai≤n， ai≠i， 1≤di≤10,000

分析：对图的特征一定要搞清楚，比如n个点n-1条边就是树，n个点n条边就是树套环，每个点出度为1就是很多链和环的结合体.为了走的最远，肯定要从入度为0的点出发，走到环上，顺着环走一遍.每次都模拟这样走一遍效率不高，因为一个环会被多次使用，所以可以先把环的长度给预处理出来，再把每个入度为0的点到环上的距离利用树形dp给算出来，因为最后不能回到自身嘛，枚举一下断点就可以了.

因为图可能不是连通的，会有多个环，所以要把所有的点都给处理到位.

暴力50分：

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = ;

int n, head[maxn], maxx,to[maxn], nextt[maxn], w[maxn], tot = , ans;

bool vis[];

long long sum;

void add(int x, int y, int z)

{

    w[tot] = z;

    to[tot] = y;

    nextt[tot] = head[x];

    head[x] = tot++;

}

void dfs(int x, int d)

{

    vis[x] = ;

    ans = max(ans, d);

    for (int i = head[x]; i; i = nextt[i])

    {

        int v = to[i];

        if (!vis[v])

            dfs(v, d + w[i]);

    }

}

int main()

{

    scanf("%d", &n);

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

    {

        int a, d;

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

        add(i, a, d);

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

        {

            dfs(i, );

            memset(vis, , sizeof(vis));

        }

        printf("%d\n", ans);return ;

}

正解：

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = ;

ll n, a[maxn], d[maxn], du[maxn], f[maxn], sum = , ans, pre[maxn], cnt, p[maxn];

bool vis[maxn];

int main()

{

    scanf("%lld", &n);

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

    {

        scanf("%lld%lld", &a[i], &d[i]);

        du[a[i]]++;

    }

    queue <ll> q;

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

        if (!du[i])

            q.push(i);

    while (!q.empty())

    {

        ll u = q.front();

        q.pop();

        ll v = a[u];

        f[v] = max(f[v], f[u] + d[u]);

        if (--du[v] == )

            q.push(v);

    }

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

        if (du[i] && !vis[i])

        {

            ll k = i;

            sum = ;

            do

            {

                vis[k] = ;

                p[++cnt] = k;

                pre[a[k]] = d[k];

                sum += d[k];

                k = a[k];

            } while (k != i);

            for (int j = ; j <= cnt; j++)

                ans = max(ans, sum + f[p[j]] - pre[p[j]]);

        }

    printf("%lld\n",ans);

    return ;

}

巴特西

noip模拟赛传球接力

最新文章

热门文章

巴特西

noip模拟赛 传球接力

最新文章

热门文章

noip模拟赛传球接力