题意
给长度为\(n\)的序列\(a[n]\)和\(b[n]\),初始时\(ans=0\),有以下操作:
问每个元素操作一次后,\(ans\)最大为多少,并输出操作序列
分析
对于一个数,如果他有前驱的话,可以考虑对于其某些前驱进行操作后再操作该数,那么画一个前驱图可以发现,这是一个拓扑排序的题,操作到某个节点时
那么拓扑排序的时候维护一个队列和一个栈,对于值大于\(0\)的节点,将其放入队列中,然后将其值加入后续节点,否则将其放入栈中(因为若连续两个节点值都小于\(0\),那么应先操作后续节点),最后输出即可
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int a[maxn], b[maxn];
vector<int> v[maxn];
int in[maxn];
void solve() {
int n;
cin >> n;
rep(i, 1, n)cin >> a[i];
rep(i, 1, n) {
cin >> b[i];
if (b[i] != -1) {
v[i].push_back(b[i]);
++in[b[i]];
}
}
int ans = 0;
queue<int> q;
rep(i, 1, n) {
if (in[i] == 0) {
q.push(i);
}
}
vector<int> tmp;
stack<int> last;
while (!q.empty()) {
int now = q.front();
if (a[now] > 0)
tmp.push_back(now);
else
last.push(now);
ans += a[now];
q.pop();
for (auto &to:v[now]) {
if (a[now] > 0)
a[to] += a[now];
--in[to];
if (in[to] == 0) {
q.push(to);
}
}
}
cout << ans << '\n';
for (auto &to:tmp)cout << to << ' ';
while (!last.empty()) {
cout << last.top() << ' ';
last.pop();
}
}
signed main() {
start;
while (T--)
solve();
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章