作者：手机用户2502900625 | 来源：互联网 | 2023-09-15 10:15
题意：给出一个n个点n条边的图且不一定连通（原题面为每个节点出度为1），相邻节点不能同时被选，每个节点有其对应价值，求最多能获得多少价值？n<=1e6,val[i]<=1e6
分析：很容易想到，如果这个图是n个点n-1条边而且连通的话，那么这个图肯定是一棵树，这用树形dp是很好实现的
dp[x][0]表示x节点不选，其子树（包括x）能产生的最大价值
dp[x][1]表达x节点选，其子树（包括x）能产生的最大价值
那么dp[x][0]+=max(dp[v][1],dp[v][0])
dp[x][1]+=dp[v][0],其中v是x的儿子
那么如果这个题是n个点n条边而且连通的话，那么这个图不就是一棵树再连上一条边，显然会是该图上得到一个环
看到环，我们之前的第一反应肯定是要缩点，但在这题中我们需要做的是将该图转化成树，也就是在环上任意位置断一条边（把这个思路积累下来吧，以前估计没做过类似做法的题）
首先在换上任意断一条边显然是不会使图不连通的，因为断开位置的两个端点依然可以利用环的剩余部分连接
那么再考虑这题的性质，设这两个断开位置的点为a，b
显然，选a的时候是不能选b的，选b的时候是不能选a的
我们在断开这条边的时候，这两个点的关系在树的意义上已经不相连了，也就是说上面那条性质也就无法实现了
所以我们必须要手动实现那条性质，
实现的方法有很多，比较朴素的就是dp[x][0/1]变成dp[x][0/1][0/1][0/1]后面两个0/1分别表示ab两点是否被选，这显然是可以做的，不过略有些复杂
可以考虑我们树中最有标志性的点或者是最易辨识的点显然是根节点
如果我们将a或b设为根节点是不是会更容易计算
注意这里设为根节点并不意味着a，b会被选
假如我们不别的限制，单纯用a为根得到完整的dp数组
显然dp[a][0]表示a不选而b可选可不选，a的子树及其自身的最大价值
dp[a][1]表示a选而b可选可不选，a的子树及其自身的最大价值
显然第二种是可能有违反那条性质的情况存在的（a选b也选），所以dp[a][1]其实对答案没啥帮助
而dp[a][0]又不能包含所有情况(他只包含a不选的情况，没有a选的情况）
所以我们需要再以b为根节点计算dp值
同理dp[b][1]是要舍掉的，
如果将ab选不选表示为0/1 0/1的话
dp[a][0]就是00和01
dp[b][0]就是00和10
而我们所需要的值是00,01和10中的最大值
这里00被计算两遍没啥影响
所以答案就是max(dp[a][0],dp[b][0])注意，这里a和b分别是以a，b为根的结果需要分开求
再回到该题上
这个图不一定连通啊
所以可能有多个这样的图（树+一条边），
那有没有可能出现树+两条边或者树呢？
不可能，因为不要光看这是一个n个点n条边的图
原题上每个节点的出度是1
也就是说，对于任意一个连通子图，他一定有节点个数条边，也就是我们说的树+一条边结构
如果出现树或树+两条边的话，显然则会出现n个点n-1条边的连通子图或者n个点n+1条边的连通子图，这就与题意不符了
所以我们需要对于每个树+一条边的结构干上述过程，然后把每个max加起来
还有我这里断边采用的是重新建图，一开始我写了个判断，但一直wa，你们也可以写写试试，教一下我这个ljQAQ
记得开longlong
代码：
#include
#include
#include
using namespace std;
#define ll long long
const int maxn=1e6+1;
struct Node
{
int to,next;
}e[maxn<<1],e2[maxn<<1];
int val[maxn];
int head[maxn];
bool vis[maxn];
int head2[maxn];
ll dp[maxn][2];
int sb[2],cnt,cnt2;
void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
void add2(int x,int y)
{
e2[++cnt2].to=y;
e2[cnt2].next=head2[x];
head2[x]=cnt2;
}
void find_sb(int x,int fa)
{
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(v!=fa)
{
if(vis[v])
{
sb[0]=x,sb[1]=v;
continue;
}
add2(v,x);add2(x,v);
find_sb(v,x);
}
}
}
void dfs(int x,int fa)
{
dp[x][1]=(ll)val[x];dp[x][0]=0ll;
for(int i=head2[x];i;i=e2[i].next)
{
int v=e2[i].to;
if(v!=fa)
{
dfs(v,x);
dp[x][0]+=max(dp[v][0],dp[v][1]);
dp[x][1]+=dp[v][0];
}
}
}
int main()
{
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&val[i],&x);
add(x,i),add(i,x);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
sb[0]=sb[1]=0;find_sb(i,-1);
dfs(sb[0],-1);ll now=dp[sb[0]][0];
dfs(sb[1],-1);ans+=max(now,dp[sb[1]][0]);
}
}
printf("%lld",ans);
return 0;
}
京公网安备 11010802041100号