Luogu_P2607 [ZJOI2008]骑士 P1453 城市环路 基环树+树形DP

Luogu_P2607 [ZJOI2008]骑士 P1453 城市环路

基环树+树形DP

---

2607
1453
题目大意都是一样的，只要相连就不能同时取
最大化权值
但是有环
那么就在搜到环之后记录(s)和(t)表示环的两边
两次树形DP
第一次强制不取(s)
第二次可取(s)
找出两个的最优解

---

P2607

单向边而且是森林，就跳(fa[])
代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1000010;
int n,val[maxn],f[maxn][2],head[maxn],tot,vis[maxn],fa[maxn],rt,ans;
struct node{
    int nxt,to;
    #define nxt(x) e[x].nxt
    #define to(x) e[x].to
}e[maxn];
inline void add(int from,int to){
    to(++tot)=to;nxt(tot)=head[from];head[from]=tot;
}
void dp(int x){
    vis[x]=1;
    f[x][0]=0;f[x][1]=val[x];
    for(int i=head[x];i;i=nxt(i)){
        int y=to(i);
        if(y==rt){
            f[y][1]=-maxn;
        }else{
            dp(y);f[x][0]+=max(f[y][1],f[y][0]);f[x][1]+=f[y][0];
        }
    }
}
void fdc(int x){
    vis[x]=1;
    rt=x;
    while(!vis[fa[rt]]){
        rt=fa[rt];vis[rt]=1;
    }
    dp(rt);
    int now=f[rt][0];
    dp(rt=fa[rt]);
    ans+=max(now,f[rt][0]);
}
signed main(){
    scanf("%lld",&n);
    for(int x,y,i=1;i<=n;i++){
        scanf("%lld%lld",&x,&y);add(y,i);f[i][1]=x;fa[i]=y;val[i]=x;
    }
    for(int i=1;i<=n;i++) if(!vis[i]) fdc(i);
    printf("%lld
",ans);
    return 0;
}

P1453

无向边且是一颗
就可以用并查集方便的求s和t

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,p[maxn],fa[maxn],f[maxn][2],ans;
struct node{
    int nxt,to;
    #define nxt(x) e[x].nxt
    #define to(x) e[x].to
}e[maxn<<1];
int head[maxn],tot,s,t;
double k;
inline int find(int x){return fa[x]==x ? fa[x] : fa[x]=find(fa[x]);}
inline void add(int from,int to){
    to(++tot)=to;nxt(tot)=head[from];head[from]=tot;
}
void dfs(int x,int fa){
    f[x][0]=0;f[x][1]=p[x];
    for(int i=head[x];i;i=nxt(i)){
        int y=to(i);
        if(y==fa) continue;
        dfs(y,x);
        f[x][0]+=max(f[y][1],f[y][0]);f[x][1]+=f[y][0];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) fa[i]=i,scanf("%d",&p[i]);
    for(int x,y,i=1;i<=n;i++){
        scanf("%d%d",&x,&y);x++;y++;
        if(find(x)==find(y)){s=x,t=y;continue;}
        add(x,y);add(y,x);fa[find(x)]=find(y);
    }
    scanf("%lf",&k);
    dfs(s,0);ans=max(ans,f[s][0]);
    dfs(t,0);ans=max(ans,f[t][0]);
    printf("%.1lf
",(double)ans*k);
    return 0;
}