acwing-1080. 骑士(基环树dp)[通俗易懂]

全栈程序员站长

发布于 2022-09-22 12:01:48

30600

代码可运行

文章被收录于专栏：全栈程序员必看全栈程序员必看

运行总次数：0

代码可运行

大家好，又见面了，我是你们的朋友全栈君。

Z 国的骑士团是一个很有势力的组织，帮会中聚集了来自各地的精英。

他们劫富济贫，惩恶扬善，受到了社会各界的赞扬。

可是，最近发生了一件很可怕的事情：邪恶的 Y 国发起了一场针对 Z 国的侵略战争。

战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡得住 Y 国的军队。

于是人们把所有希望都寄托在了骑士团身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。

骑士团是肯定具备打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。

每个骑士有且仅有一个他自己最厌恶的骑士（当然不是他自己），他是绝对不会与最厌恶的人一同出征的。

战火绵延，人们生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！

国王交给你了一个艰巨的任务：从所有骑士中选出一个骑士军团，使得军团内没有矛盾的两人，即不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况，并且使这支骑士军团最富有战斗力。

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

输入格式输入第一行包含一个正整数 N，描述骑士团的人数；

接下来 N 行每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

输出格式输出包含一行，一个整数，表示你所选出的骑士军团的战斗力。

数据范围 N≤106, 每名骑士的战斗力都是不大于 106 的正整数。

输入样例：
3
10 2
20 3
30 1
输出样例：
30

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 2 * N;
const int INF = 0x003f3f3f3f3f3f3f;
typedef long long ll;
struct Edge{ 
   
    int v,next;
}edge[M];
int val[N];
int head[N],cnt;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
ll f[N][2];
int ins[N],st[N],rm[M];
ll ans = 0;
void dfs(int u,int f,int from);
void dfs_c(int u,int from){ 
   
    st[u] = ins[u] = true;
    for(int i = head[u];~i;i = edge[i].next){ 
   
        if(i == (from ^ 1))continue;
        int v = edge[i].v;
        if(!st[v])dfs_c(v,i);
        else if(ins[v]){ 
   
            ans = 0;
            rm[i] = rm[i ^ 1] = true;
            memset(f,0,sizeof f);
            dfs(v,-1,-1); // 不选v u可以选可以不选
            ans = max(ans,f[v][0]);
            memset(f,0,sizeof f);
            dfs(v,u,-1);    //选v u一定不选
            ans = max(ans,f[v][1]);
            rm[i] = rm[i ^ 1] = false;
        }
    }
    ins[u] = false;
}
void dfs(int u,int ff,int from){ 
   
    f[u][0] = 0,f[u][1] = val[u];
    for(int i = head[u];~i;i = edge[i].next){ 
   
        if(rm[i] || i == (from ^ 1))continue;
        int v = edge[i].v;
        dfs(v,ff,i);
        f[u][0] += max(f[v][1],f[v][0]);
        f[u][1] += f[v][0];
    }
    if(ff == u)f[u][1] = -INF;
}
ll res = 0;
int main(){ 
   
    memset(head,-1,sizeof head);
    cnt = 0;
    int n,x;
    cin>>n;
    for(int i = 1;i <= n;i ++){ 
   
        scanf("%d %d",&val[i],&x);
        add(i,x),add(x,i);
    }
    for(int i = 1;i <= n;i ++)
    { 
   
        if(!st[i]){ 
   
            dfs_c(i,-1);
            res += ans;
        }
    }
    cout<<res<<endl;
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168538.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java