花式把妹

【问题描述】

	保镖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;
}

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