BZOJ5289 洛谷4437：[HNOI/AHOI2018]排列——題解

https://www.lydsy.com/JudgeOnline/problem.php?id=5289

https://www.luogu.org/problemnew/show/P4437

考慮對于a[i]=m,a[m]=n，我們令p[j]=i,p[k]=m（一定會有一對(j,k)滿足這個條件的），則我們會有p[k]=a[p[j]]，此時我們要滿足k<j，也就是a[m]放的位置要比a[i]靠前。

也就是說選第m個之后才能選第i個。

轉換成圖論模型就是m->i <=> a[i]->i。

那么問題豁然開朗，首先如果圖中有環就能判斷無解了。

如果有解則必然為以0為根的有向樹，則答案為每個節點i被拿到的時間*w[i]（前提是i的父親被拿才可以拿i）。

再考慮最大化答案，則我們讓樹中最小值min盡可能早的被拿到就好了。

繼續貪心，則如果當前局面能夠拿到min則一定拿min，換句話將就是拿了min的父親就一定拿min。

那么父親和min之間就成了捆綁關系，于是將其縮起來，在縮的過程中更新答案，然后遞歸這個過程就好了。

每次找min可以用堆維護，復雜度O(nlogn)。

（PS：更新答案，每次更新顯然是這個點前面一些點被選了，于是它一定產生了前面這些點個數*w[該點]的價值）

那么就需要考慮我們縮完的點的w要怎么計算，對于兩個集合a，b要合并，顯然用在計算上的w=wa+wb，但是用堆排序的時候就不能這么做了。

自然能想到取平均值，雖然我不會證明，不過考量一下發現差不多。

#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
typedef long double dl;
typedef pair<dl,int>pii;
#define fi first
#define se second
typedef __gnu_pbds::priority_queue<pii,greater<pii>,__gnu_pbds::pairing_heap_tag> heap;
const int N=5e5+5;
inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X;
}
struct node{int to,nxt;
}e[N];
int n,cnt,head[N],vis[N],a[N],num,fa[N],size[N];
ll w[N],ans;
heap::point_iterator id[N];
heap q;
inline void add(int u,int v){e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
bool dfs(int u){vis[u]=1;num++;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(vis[v]||!dfs(v))return 0;}if(!u&&num<=n)return 0;return 1;
}
inline int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
int main(){n=read();for(int i=1;i<=n;i++)a[i]=read(),add(a[i],i);for(int i=1;i<=n;i++)w[i]=read();if(!dfs(0)){puts("-1");return 0;}for(int i=0;i<=n;i++)fa[i]=i,size[i]=1;for(int i=1;i<=n;i++)id[i]=q.push(pii(w[i],i));while(!q.empty()){int u=q.top().se,v=a[u];q.pop();int rt=find(v);ans+=w[u]*size[rt];fa[u]=rt;w[rt]+=w[u];size[rt]+=size[u];if(rt)q.modify(id[rt],pii((dl)w[rt]/size[rt],rt));}printf("%lld\n",ans);return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

?+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

?+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++