题目描述

Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。

最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。

骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。

战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。

为了描述战斗力，我们将骑士按照 1 至 n 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

解法

这道题的图一定是若干个不连通的基环树，考虑到一条边的限制是两边不能同时选，我们先将一个边的限制确定了，再对整棵树跑没有上司的舞会，所以我们就取环上的一对点，跑两次d p dpdp，每次限制某一个点一定不能选，这道题细节有点多，详细看代码。

题解

#include <cstdio>//by hetao5487227
#include <iostream>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
const int MAXN = 1000005;
int read()
{
	int x=0,flag=1;char c;
	while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
	while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*flag;
}
int n,x,y,tot,ans,f[MAXN],pd[MAXN],vis[MAXN]；
int vis2[MAXN],val[MAXN],dp[MAXN][2];//0/1 选/不选 
struct edge
{
	int v,next;
}e[MAXN*2];
void find(int u,int fa)//找环 
{
	vis[u]=pd[u]=1;//vis判断是否访问，pd找环只找反祖边（卡掉二元环） 
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		if(pd[v])//找到了返祖边，有环 
		{
			x=u;y=v;
			continue;
		}
		if(vis[v]) continue;//只能向没有标记的地方跑 
		find(v,u);
		pd[v]=0;//只能找返祖边，所以清零 
	}
}
void dfs(int u,int fa)
{
    vis2[u]=1;//判断访问过没有 
	if(dp[u][0]!=-inf) dp[u][0]=val[u]; 
	dp[u][1]=0;//赋初值 
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(vis2[v] || (u==x && v==y) || (u==y && v==x)) continue;
		//只能走没访问过的点，不能走返祖边 
		dfs(v,u);
		dp[u][0]+=dp[v][1];//没有上司的舞会 
		dp[u][1]+=max(dp[v][1],dp[v][0]);
	}
}
void clear(int u,int fa)//清空vis2 
{
	vis2[u]=0;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(vis2[v]) clear(v,u);
	}
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		val[i]=read();int j=read();
		e[++tot]=edge{j,f[i]},f[i]=tot;
		e[++tot]=edge{i,f[j]},f[j]=tot;
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			int Max=0;
			x=y=0;
			find(i,0);
			dp[x][0]=-inf;//限制x不能选 
			dfs(i,0);
			clear(i,0);//清空vis2 
			Max=max(Max,max(dp[i][0],dp[i][1]));
			dp[x][0]=0;//清除标记 
			dp[y][0]=-inf;//限制y不能选 
			dfs(i,0);
			Max=max(Max,max(dp[i][0],dp[i][1]));
			dp[y][0]=0;
			ans+=Max;//每个基环树的最大值求和 
		}
	printf("%lld\n",ans);
}

认真读完题目我们会发现

因为一个骑士有且只有一个最讨厌的人

而且这个骑士不会讨厌自己

即该图中是没有自环的

所以 考虑这个图

我们把x所讨厌的人y设为x的父亲节点

这样考虑每一个人都有且只有一条出边

所以对一个"联通块"

只有根节点有机会形成环

即环一定包含根节点

为什么呢?

因为一个点的出度只能为1

考虑非根节点

它的出度一定是贡献给它的父亲的

而根节点它的出度只能贡献给它的后代

(这里的"根节点""叶子节点"都只是为了描述方便,并不严谨,也许可以理解为"删边以后的叶子和根"?)

所以我们又解决了一个问题:

每个联通块内有且只有一个简单环

这样 我们考虑把每个联通块的环上删一条边

这样它必然构成树

然后要注意

删掉的边所连接的两点x,y

是不能同时选的

所以我们分别强制x,y其中一个点不选

对新树跑DP

显然相邻的点是不能选的

所以得到状态转移方程:

用f[i][0/1]表示以i为根节点的子树选i/不选i所能获得的最大价值

则 f[i][0]=sigema(max(f[son][0],f[son][1])); for each son of i

f[i][1]=sigema(f[son][0]); for each son of i

应该就很清楚了

再一个细节就是答案会爆int

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 2000000
using namespace std;
int n,cnt;
long long ans;
int root;
long long f[maxn][2];
int head[maxn],val[maxn],vis[maxn],fa[maxn];
struct edge
{
    int pre,to;
}e[maxn];
inline void add(int from,int to)
{
    e[++cnt].pre=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}
void dp(int now)
{
    vis[now]=1;
    f[now][0]=0,f[now][1]=val[now];
    for(int i=head[now];i;i=e[i].pre)
    {
        int go=e[i].to;
        if(go!=root)
        {
            dp(go);
            f[now][0]+=max(f[go][1],f[go][0]);
            f[now][1]+=f[go][0];
        }
        else
        {
            f[go][1]=-maxn;
        }
    }
}
inline void find_circle(int x)
{
    vis[x]=1;
    root=x;
    while(!vis[fa[root]])
    {
        root=fa[root];
        vis[root]=1;

}//找环

dp(root);
    long long t=max(f[root][0],f[root][1]);
    vis[root]=1;
    root=fa[root]; 
    dp(root);
    ans+=max(t,max(f[root][0],f[root][1]));
    return;
}
inline int in()
{
    char a=getchar();
    while(a<'0'||a>'9')
    {
        a=getchar();
    }
    int t=0;
    while(a<='9'&&a>='0')
    {
        t=(t<<1)+(t<<3)+a-'0';
        a=getchar();
    }
    return t;
}
//写一下伪代码 
//在存的时候存一下每个人最讨厌的人为他的父亲
//对每个没访问的点DFS 
//在这个没访问的点所在的连通块上找环
//找到以后强制不选它的父亲对它进行DP
//然后强制不选它对它的父亲进行DP
//然后取一个最大值即可 
//在DP里面
//先考虑f[x][0]是不选x,初始值为0
//f[x][1]是选x,初值为val[x]
//这是一个很好的赋值方法
//然后跑DP就行了 
int main()
{
    n=in();
    for(int i=1;i<=n;i++)
    {
        val[i]=in();
        int x=in();
        add(x,i);
    //    add(i,x);
        fa[i]=x;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            find_circle(i);
        }
    }
    printf("%lld\n",ans);
    return 0;
}