8
30
2015
0

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

 花式把妹

【问题描述】

	保镖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: 154

登录 *


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