Codeforces Round #660 (Div. 2) Captain Flint and Treasure 拓扑排序（按照出度、入读两边拓扑排序）

V2AS问路

Codeforces Round #660 (Div. 2) Captain Flint and Treasure 拓扑排序（按照出度、入读两边拓扑排序）

阅读原文时间：2023年07月09日阅读：3

题目链接：Captain Flint and Treasure

题意：

一种操作为选一个下标使得ans+=a[i] 且把a[b[i]]+a[i] 要求每个下标都进行一种这样的操作，问怎么样的操作顺序才能使得ans最大

题解：

在题目面板的输入里面说了这是一个有向无环图，我怎么没看到题目上说这是一个图？

我们可以把那个操作当作一条边，而且那个操作还是单向的，所以就成有向无环图了

如果a[i]>=0，那么肯定需要进行这种操作（因为会增加ans的值）。如果a[i]为负数，那么肯定是尽量减少这种操作

那么对于a[i]>=0的数，我们对入度为0的点进行拓扑排序，以使得a[i]尽可能的为最后的答案ans做贡献

对于a[i]<0的数，那么就从出度为0的点开始进行拓扑排序

代码：

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #define fi first
10 #define se second
11 #define pb push_back
12 using namespace std;
13 typedef long long ll;
14 const int maxn=2e5+10;
15 const int mod=1e9+7;
16 const double eps=1e-8;
17 ll a[maxn];
18 ll b[maxn];
19 ll ru[maxn];
20 ll chu[maxn];
21 vectorE[maxn];
22 vectorG[maxn];
23 ll vis[maxn];
24 int main()
25 {
26 ios::sync_with_stdio(false);
27 cin.tie(0);
28 ll n;
29 cin>>n;
30 ll sum=0;
31 for(ll i=1;i<=n;i++) 32 { 33 cin>>a[i];
34 }
35 for(ll i=1;i<=n;i++) 36 { 37 cin>>b[i];
38 }
39 vectorans;
40 for(ll i=1;i<=n;i++) 41 { 42 if(b[i]==-1) 43 continue; 44 ru[b[i]]++; 45 chu[i]++; 46 E[i].pb(b[i]); //存放正向边的vector 47 G[b[i]].pb(i); //存放逆向边的vector 48 } 49 queueq;
50 for(ll i=1;i<=n;i++) //找出入度为0的点，并从此开始进行拓扑排序 51 { 52 if(ru[i]==0) //而且我们只处理ai值大于0的点 53 { 54 q.push(i); 55 } 56 } 57 while(!q.empty()) 58 { 59 ll u=q.front(); 60 q.pop(); 61 for(auto &v:E[u]) 62 { 63 ru[v]--; 64 if(a[u]>=0) //根据题目描述一个点i指向下一个点b[i]，那么这个边只会有一条，所以u这个点虽然在for循环
65 { //内，但是这个循环只会循环一次
66 a[v]+=a[u];
67 sum+=a[u];
68 ans.pb(u); //ans存放路径，因为最后要输出
69 vis[u]=1;
70 }
71 if(ru[v]==0)
72 {
73 q.push(v);
74 }
75 }
76 }
77 queuer;
78 for(ll i=1;i<=n;i++)
79 {
80 if(chu[i]==0&&vis[i]==0)
81 {
82 r.push(i);
83 }
84 }
85 while(!r.empty())
86 {
87 ll u=r.front();
88 r.pop();
89 if(vis[u]==0)
90 {
91 sum+=a[u];
92 ans.pb(u);
93 }
94 for(auto &v:G[u])
95 {
96 chu[v]--;
97 if(chu[v]==0)
98 r.push(v);
99 }
100 }
101 printf("%lld\n",sum);
102 ll len=ans.size();
103 for(ll i=0;i<len;++i)
104 {
105 // if(i==len-1)
106 // printf("%lld\n",ans[i]);
107 // else
108 printf("%lld ",ans[i]);
109 }
110 return 0;
111 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) C.Producing Snow

Codeforces Round #576 (Div. 2)

Codeforces Round #769 (Div. 2) - D. New Year Concert

Codeforces Global Round 8 B. Codeforces Subsequences（构造）

CF1486X Codeforces Round #703

Codeforces Round #601 (Div. 2) A-E

Usmjeri(COCI2017.2)题解

Codeforces Round #776 (Div

Codeforces Round #647 (Div. 2) - Thanks, Algo Muse! D. Johnny and Contribution (贪心,模拟)

Codeforces Round #671 (Div. 2) B. Stairs (递推)