8
30
2015
1

【缩点+优先队列+罗干】花式把妹

 花式把妹

【问题描述】

	保镖SHC有n个妹子(妹子1到n编号),某些妹子与某个对应的妹子(单向)关系非常好,只要SHC搞
定了这个妹子,也能顺手搞定那个对应的妹子。每个妹子颜值不同,当这个妹子被搞定后就能SHC的后宫群总
颜值会增加对应颜值。现在。SHC作为外貌协会会长,他想手动搞定k个妹子,来为他的后宫群增加最多的颜值。

【输入格式】

	第1行两个整数 n、k。
	接下来n行每行两个整数a[i]、b[i]。a[i]表示第i个妹子非常要好的妹子,如果a[i]为0,则表示
这个妹子非常高贵冷艳,没有要好的妹子。b[i]表示这个妹子的颜值。

【输出格式】

	仅一个数,表示保镖SHC后宫群增加最多的颜值。

魔泥赛(题面已修改),场上只能乱搞。。。

根据各种脑补猜测:每次引爆当前最大的链一定是最优解。

于是这题就成了维护一个森林上的许多链。

等等,谁告诉你这是森林的!

仔细看题,考虑到每个连通分量里最多只有一个环……

就可以缩点辣,而且环一定缩成树根!

缩点出现森林后,我们可以大法师出所有子树的最大链(链上权值和)。

把树根的最大链作为值鏼入优先队列里。

以后砍链就找到队首,一路沿着最大的子链砍下去,把砍剩下的“枝条”再加入森林(优先队列)。(woc扦插大法好)

那么这题就罗过去了w。注意long long。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<algorithm>
#define maxn 200010
using namespace std;
typedef long long LL;
//原题相关
int a[maxn];
int n,k;
vector<int>G[maxn];
LL w[maxn],W[maxn];
//树操作相关 
LL ans=0;
struct Ch{int t;};
struct Poi{int x;};
vector<Ch>ch[maxn];
int X[maxn];
int cmp(Ch a,Ch b){return X[a.t]>X[b.t];}
priority_queue <Poi> Q;//当前森林中X值最大的根 
bool operator<(Poi a,Poi b){return X[a.x]<X[b.x];}
void Split(int u)
{
	if (!ch[u].size()) return;
	sort(ch[u].begin(),ch[u].end(),cmp);
	for (int i=1;i<ch[u].size();i++)
		Q.push((Poi){ch[u][i].t});
	Split(ch[u][0].t);
}
void Bomb()
{
	Poi x=Q.top();
	Q.pop();
	ans+=X[x.x];
	Split(x.x);
}

//大法师相关
int v[maxn];
LL Dfs(int u)
{
	v[u]=1;
	LL ans=0;
	for (int i=0;i<ch[u].size();i++)
	{
		ans=max(ans,Dfs(ch[u][i].t));
	}
	return X[u]=ans+W[u];
}
int stack[maxn],Top=0;
int bc[maxn],bcn=0;
void dfs(int u) 
{	
	if (!a[u]||a[u]==u)
	{
		bc[u]=++bcn;
		W[bcn]+=w[u];
		return;
	}
	if (v[u]==1)
	{
		bc[u]=++bcn;
		W[bcn]+=w[u];
		Top--;
		while (stack[Top]!=u) 
		{
			bc[stack[Top]]=bcn;
			W[bcn]+=w[stack[Top]];
			Top--;
		}
		return;
	}	
	v[u]=1;
	for (int i=0;i<G[u].size();i++)
	{
		stack[++Top]=G[u][i];	
		dfs(G[u][i]);
		Top--;
	}
	v[u]=2;
}
 
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		int u;
		scanf("%d%d",&a[i],&w[i]);
		G[a[i]].push_back(i);
	}
	//大法师相关 
	for (int i=1;i<=n;i++)
	{
		Top=0;
		stack[0]=i;
		if (!v[i]) dfs(i);
	}
	//重构图相关 
	int K=bcn;//树根 
	for (int i=1;i<=n;i++)
		if (!bc[i]) bc[i]=++K,W[bc[i]]=w[i];
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<G[i].size();j++)
			if (bc[i]!=bc[G[i][j]])
			{
				ch[bc[i]].push_back((Ch){bc[G[i][j]]});
			}
	}
	//维护新森林 
	memset(v,0,sizeof(v));
	for (int i=1;i<=bcn;i++)
	{
		Dfs(i);
		Q.push((Poi){i});
	}
	//罗干 
	for (int i=1;i<=k;i++)
		if (Q.size()) Bomb();
	printf("%lld",ans);
	return 0;
}

为什么作为一个数组选手写得比指针选手长

Category: HDU | Tags: 缩点 优先队列 伪树剖 | Read Count: 557
villa cleaning servi 说:
2021年11月15日 22:33

Cleaning service Brigade cleans many kinds of houses, including single-family properties, apartment things, and condo properties. They strive for excellence inside their cleaning companies, and simply hire one of the most dependable and also trustworthy staff. An substantial recruiting method is implemented, and each manager will discover ways to pick excellent potential employees independent of the bad. Since they strive regarding excellence, slacking off just isn't permitted.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com