洛谷 U138349 全军出击

洛谷 U138349 全军出击

洛谷传送门

题目背景

SeawaySeawa**y所效命的AlphaAlpha国和邪恶的EulerEuler国爆发了战争。由于AlphaAlpha国间谍的出色渗透，EulerEuler国节节败退。现在，全面反攻的时刻就要来了！AlphaAlpha国人民委员会发布命令：全军出击！把EulerEuler鬼子赶到海里！

题目描述

AlphaAlpha国的特种部队是军队精锐中的精锐。每位士兵都是层层选拔出的“兵王”。但是与强大的实力对应的是古怪的脾气，他们每个人都有且仅有一个最讨厌的同事。他们绝不与最讨厌的同事并肩作战！战斗迫在眉睫，但是特种部队还在出征人员名单上争论不休。AlphaAlpha国军队总司令RoseRos**e震怒，她命令Alpha国总参谋长SeawaySeawa**y火速解决这个问题。

SeawaySeawa**y了解到，每个士兵有自己的战斗力p_ip**i。SeawaySeawa**y的任务是：安排一份让所有人都满意的出征名单，并使得出征的所有士兵的总战斗力尽可能大。

输入格式

从文件ace.inace.i**n中读入数据。
​ 第一行包括一个整数NN，表示特种部队的总人数。​
​ 接下来的NN行，每行22个整数，分别描述每个士兵的战斗力和他最讨厌的同事。

输出格式

输出到文件ace.outace.out中。 仅一行一个整数，表示你制定的出征名单的最大总战斗力。

---

题解：

基环树DP裸题。

很容易看出是一个基环树。

基环树求最大点权独立集。

如果没有基环树那会很爽，给谁谁切。但是一基环就变成紫题了。

给了枚举全排列30分，够良心了。给了暴力断环70分，更良心了。

正解就是断环之后跑两次树形DP，分别计算影响。注意，两次树形DP都必然是0的情况。防止这个环加上去之后造成错误。

原题给的是基环树森林，但是鄙人不会造，所以只造了一棵基环树。还是比较弱的。

代码：

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e6+10;
int n,cnt;
int p[maxn],ene[maxn];
int tot,head[maxn],to[maxn<<1],nxt[maxn<<1];
int sub[maxn];
bool v[maxn],flag;
ll dp[maxn][2];
int p1,p2;
ll ans;
int par[maxn<<1];
void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs1(int x,int f)
{
	v[x]=1;
	sub[++cnt]=x;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==f)
			continue;
		if(!v[y])
			dfs1(y,x);
		else if(v[y]&&!flag)
		{
			flag=1;
			p1=x,p2=y;
		}
	}
}
void dfs2(int x,int f)
{
	dp[x][0]=0;
	dp[x][1]=p[x];
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(!y||y==f)
			continue;
		dfs2(y,x);
		dp[x][0]+=max(dp[y][0],dp[y][1]);
		dp[x][1]+=dp[y][0];
	}
}
void work()
{
	if(!flag)
	{
		dfs2(sub[1],0);
		ans+=max(dp[sub[1]][1],dp[sub[1]][0]);
	}
	else
	{
		ll tmp=-1;
		for(int i=head[p1];i;i=nxt[i])
		{
			int y=to[i];
			if(y==p2)
			{
				to[i]=0;
				to[par[i]]=0;
				break;
			}
		}
		dfs2(p1,0);
		tmp=max(tmp,dp[p1][0]);
		dfs2(p2,0);
		tmp=max(tmp,dp[p2][0]);
		ans+=tmp;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&p[i],&ene[i]);
		add(i,ene[i]);
		add(ene[i],i);
		par[tot]=tot-1;
		par[tot-1]=tot;
	}
	for(int i=1;i<=n;i++)
		if(!v[i])
		{
			cnt=0;
			flag=0;
			dfs1(i,0);
			work();
		}
	printf("%lld",ans);
	return 0;
}