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

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

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

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

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

题目链接🔗

[ZJOI 2008] 骑士

题解

基数环版没有上司的舞会
把环拆开,两头分别做一次舞会,求最大值即可

代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e6+10;
int vis[maxd],arr[maxd];
long long dp[maxd][2],ans;
int a,b,n,x,k;
struct node
{
    int v,net;
}e[2*maxd];
int f[maxd],eid;
void insert(int x,int y)
{
    e[eid].net = f[x];
    e[eid].v = y;
    f[x] = eid++;
}
void dfs(int x,int last)
{
    vis[x] = 1;
    for(int i=f[x];i+1;i=e[i].net)
    {
        if((i^1)==last) continue;
        int v = e[i].v;
        if(vis[v]) a=x,b=v,k=i;
        else dfs(v,i);
    }
}
void dp_dfs(int x,int last)
{
    dp[x][0] = 0;
    dp[x][1] = arr[x];
    for(int i=f[x];i+1;i=e[i].net)
    {
        if((i^1)==last) continue;
        if(i==k||(i^1)==k) continue;
        dp_dfs(e[i].v,i);
        dp[x][0] += max(dp[e[i].v][1],dp[e[i].v][0]);
        dp[x][1] += dp[e[i].v][0];
    }
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    memset(f,-1,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&arr[i],&x);
        insert(i,x);insert(x,i);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        dfs(i,-1);
        dp_dfs(a,-1);
        long long temp = dp[a][0];
        dp_dfs(b,-1);
        ans += max(dp[b][0],temp);
    }
    printf("%lld",ans);
    return 0;
}