首页 > 其他分享 >【HNOI_AHOI2018】排列(树上一类全序问题)

【HNOI_AHOI2018】排列(树上一类全序问题)

时间:2022-10-28 20:47:38浏览次数:43  
标签:sz ch AHOI2018 int 总权值 HNOI cdot 全序 ans

这个条件给的有点诡异:对于任意的 \(a_{p_j}=p_k\),都有 \(k<j\)。

那么对于某个 \(a_x=y\),意思就是 \(y\) 在 \(p\) 中的位置小于 \(x\) 在 \(p\) 中的位置。

那么如果我们连边 \((a_x,x)\),就是要求图中没有环,是一棵树,而且父亲在 \(p\) 中的位置要小于儿子在 \(p\) 中的位置。

再看一下要求:按 \(p\) 的顺序把 \(i\times w_{p_i}\) 加起来得到总权值,找到一种 \(p\) 的顺序使得总权值最大。

是个树上全序问题(可参考 AGC023F),现在有若干个连通块,我们要给这些连通块一种顺序使得总权值最大。

仍然考虑最优顺序下,相邻的两个连通块 \(a\) 和 \(b\),它们的大小分别为 \(sz_a,sz_b\),它们各自的 \(w\) 的和分别为 \(W_a,W_b\),它们各自的总权值分别为 \(V_a,V_b\)。设 \(a\) 之前的总权值为 \(V\),\(a\) 之前的点的总数为 \(S\)。

交换前:\(ans_1=V+S\cdot W_a+V_a+(S+sz_a)\cdot W_b+V_b\)。

交换后:\(ans_2=V+S\cdot W_{b}+V_b+(S+sz_b)\cdot W_a+V_a\)。

强制令 \(ans_1\geq ans_2\),得到 \(\dfrac{W_a}{sz_a}\leq \dfrac{W_b}{sz_b}\),于是我们直接按 \(\dfrac{W_a}{sz_a}\) 从小到大排序即可。

#include<bits/stdc++.h>

#define N 500010
#define ll long long

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

int n,fa[N],rt[N];
int sz[N];
ll w[N],v[N];
bool vis[N];
bool del[N];

vector<int>e[N];

void dfs(int u)
{
	if(vis[u])
	{
		puts("-1");
		exit(0);
	}
	vis[u]=1;
	for(int v:e[u]) dfs(v);
}

int find(int x)
{
	return x==rt[x]?x:(rt[x]=find(rt[x]));
}

struct cmp
{
	inline bool operator()(int a,int b) const//这里加inline会大大地优化时间,不然过不去
	{
		if(w[a]*sz[b]==w[b]*sz[a]) return a<b;
		return w[a]*sz[b]<w[b]*sz[a];
	}
};

set<int,cmp>s;

int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		rt[i]=i;
		fa[i]=read();
		if(fa[i]) e[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)
		if(!fa[i]) dfs(i);
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			puts("-1");
			return 0;
		}
	}
	for(int i=1;i<=n;i++)	
		v[i]=w[i]=read(),sz[i]=1;
	for(int i=1;i<=n;i++)
		s.insert(i);
	del[0]=1;
	ll V=0,S=0;
	while(!s.empty())
	{
		int u=(*s.begin());
		s.erase(s.begin());
		int f=find(fa[u]);
		if(del[f])
		{
			del[u]=1;
			V+=S*w[u]+v[u];
			S+=sz[u];
			continue;
		}
		s.erase(f);
		rt[u]=f;
		v[f]+=sz[f]*w[u]+v[u];
		w[f]+=w[u];
		sz[f]+=sz[u];
		s.insert(f);
	}
	printf("%lld\n",V);
	return 0;
}

标签:sz,ch,AHOI2018,int,总权值,HNOI,cdot,全序,ans
From: https://www.cnblogs.com/ez-lcw/p/16837425.html

相关文章

  • 【HDU6326】Monster Hunter(树上一类全序问题)
    先考虑没有树的限制,即我们可以任意安排顺序打怪兽,那么这就是一个全序问题。考虑在某种顺序下,假设初始血量为\(st\),那么打到第\(i\)个怪物时剩余的血量就是\(st+\sum\l......
  • 【AGC023F】01 on Tree(树上一类全序问题)
    显然如果没有树的限制,我们优先选\(0\),然后选\(1\)。如果有了树的限制,我们考虑下面这么一种贪心方法:假设当前能够选的点的集合为\(S\)(初始时\(S\)只包含根),然后选出\(......
  • 洛谷P3225 [HNOI2012]矿场搭建
    SLOJH7136.「HNOI2012」矿场搭建题目描述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援......
  • BZOJ 2733: [HNOI2012]永无乡
    题目链接:​​传送门​​​Description永无乡包含n座岛,编号从1到n,每座岛都有自己的独一无二的重要度,按照重要度可以将这n座岛排名,名次用1到n来表示。某些岛之间......
  • BZOJ 1008: [HNOI2008]越狱
    题目链接:​​传送门​​早做过的我们用全部的方案数减去不越狱的方案数全部的方案数就是是宗教数是房间数保证不越狱的话第一个房间的罪犯有种宗教可以选择剩下的个房......
  • BZOJ 1185([HNOI2007]最小矩形覆盖-旋转卡壳+点集几何意义)
    1185:[HNOI2007]最小矩形覆盖TimeLimit: 10Sec  MemoryLimit: 162MBSec  SpecialJudgeSubmit: 258  Solved: 137Description l要事先改成......
  • BZOJ 1189([HNOI2007]紧急疏散evacuate-网络流二分+拆点)
    发生了火警,所有人员需要紧急疏散!假设每个房间是一个NM的矩形区域。每个格子如果是’.’,那么表示这是一块空地;如果是’X’,那么表示这是一面墙,如果是’D’,那么表示这是一扇门......
  • 题解 P2224 [HNOI2001]产品加工
    一道很有趣的dp题。这道题是以答案为下标来设定状态,在这种生产问题这个套路还是挺常见的,需要积累一下。我们令\(f_{i,j}\)为前\(i\)个任务\(A\)机器花了\(j\)时......
  • 洛谷 P3224 [HNOI2012]永无乡 题解
    查询第\(k\)小值想到权值线段树。合并操作想到线段树合并。维护连通性想到并查集。并查集合并方向应与线段树合并方向一致。查询时,先求出并查集的根再在线段树上询......
  • [HNOI2015]亚瑟王
    题面首先可以知道的是,牌与牌之间的期望收益互相不影响,所以我们对每种牌分开进行计算。所以我们设出状态,\(f_{i,j}\)到第\(i\)种牌,已经过了\(j\)轮,第\(i\)种牌抽到......