P8269 [USACO22OPEN] Visits S

题目描述

Bessie 的 $N$（$2\le N\le 10^5$）个奶牛伙伴（编号为 $1\cdots N$）每一个都拥有自己的农场。对于每个 $1\le i\le N$，伙伴 i 想要访问伙伴 $a_i$（$a_i\ne i$）。

给定 $1\dots N$ 的一个排列 $(p_1,p_2,\dots ,p_N)$，访问按以下方式发生。

对于 $1$ 到 $N$ 的每一个 $i$：

• 如果伙伴 $a_{p_i}$ 已经离开了她的农场，则伙伴 $p_i$ 仍然留在她的农场。
• 否则，伙伴 $p_i$ 离开她的农场去访问伙伴 $a_{p_i}$ 的农场。这次访问会产生快乐的哞叫 $v_{p_i}$ 次（$0\le v_{p_i}\le 10^9$）。

对于所有可能的排列 $p$，计算所有访问结束后可能得到的最大哞叫次数。

输入格式

输入的第一行包含 $N$。

对于每一个 $1\le i\le N$，第 $i+1$ 行包含两个空格分隔的整数 $a_i$ 和 $v_i$。

输出格式

输出一个整数，为所求的答案。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 “long long”）。

输入输出样例 #1

输入 #1

4
2 10
3 20
4 30
1 40

输出 #1

90

说明/提示

【样例解释】

如果 $p=(1,4,3,2)$，则

• 伙伴 $1$ 访问伙伴 $2$ 的农场，产生 $10$ 次哞叫。
• 伙伴 $4$ 看到伙伴 $1$ 已经离开了农场，所以无事发生。
• 伙伴 $3$ 访问伙伴 $4$ 的农场，又产生 $30$ 次哞叫。
• 伙伴 $2$ 看到伙伴 $3$ 已经离开了农场，所以无事发生。

这样总计得到了 $10+30=40$ 次哞叫。

另一方面，如果 $p=(2,3,4,1)$，则

• 伙伴 $2$ 访问伙伴 $3$ 的农场，产生 $20$ 次哞叫。
• 伙伴 $3$ 访问伙伴 $4$ 的农场，产生 $30$ 次哞叫。
• 伙伴 $4$ 访问伙伴 $1$ 的农场，产生 $40$ 次哞叫。
• 伙伴 $1$ 看到伙伴 $2$ 已经离开了农场，所以无事发生。

这样总计得到了 $20+30+40=90$ 次哞叫。可以证明这是所有可能的排列 $p$ 中访问结束后得到的最大可能的哞叫次数。

C++实现

#include<bits/stdc++.h>
using namespace std;
#define inf 1e18+10
#define int long long
const int maxn=100010;
int n,a[maxn],v[maxn],rd[maxn],ans,minn=inf;
bool vis[maxn];
queue<int>q;
void topo(){
    for(int i=1;i<=n;i++){
        if(!rd[i])q.push(i);
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        ans+=v[x];rd[a[x]]--;
        vis[x]=1;
        if(!rd[a[x]])q.push(a[x]);
    }
    return;
}
void dfs(int x){
    vis[x]=1;
    minn=min(minn,v[x]);
    if(vis[a[x]])return;
    dfs(a[x]);
    return;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i],&v[i]);
        rd[a[i]]++;
    }
    topo();
    for(int i=1;i<=n;i++){
        if(!vis[i])ans+=v[i];
    }
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        minn=inf;dfs(i);
        ans-=minn;
    }
    printf("%lld",ans);
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容