Fireworks 题解

· · 题解

题解时间

subtask 1

一个简单的环套树 DP。

每个关系一都建 1 条边，然后正常地 DP 就行了。

DP 就很简单，一个使用根，一个不使用根，然后取 max。

最后所有基环树的 asw 之和即为所求。

subtask 2

在 subtask 2 的基础上有了关系二。

因为每个系列都要一起选，所以就从选点变成了选系列，所以可以把每个系列的所有点都缩成一个点，每个系列的权值为其中所有的烟花的权值之和。(没有系列的烟花当成一个系列，主烟花为自己)

其中的每个烟花的关系一，如果与主烟花的关系一是一个系列的，就把这两个系列之间的边的权值加上这个关系一的权值。如果这个烟花的关系一与这个烟花是同一个系列的，就把这个系列的权值减去这个关系一的权值。

用并查集找环，但有可能一个系列的主烟花的关系一与这个烟花为同一个系列，所以这是一个 树加基环树 森林。再利用建反边，便可解决问题。

把有入度的点标记一下，这样没别标记的点为一个树的根，再在找到环的时候把两个点记录下来，作为基环树的根，最后依次 DP，把每次得到的结果加和，就是答案。

注：记得开 long long.

最后附上 std:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
vector<int>mm[500001];
struct nood {
    int to,next;
    long long v;
} g[1000001];
int num,m,top,cnt,n,fa[500001],fa1[500001],a[500001];
int xx[500001],root[500001],di[500001],zhi[500001],zhu[500001];
long long ans,f[500001][2],v[500001],vv[500001],ji[500001];
bool vi[500001];
char hhd;
inline void read1(int &k) {
    k=0,hhd=getchar();
    while(hhd>'9'||hhd<'0') hhd=getchar();
    while(hhd<='9'&&hhd>='0') k=k*10+hhd-'0',hhd=getchar();
}
inline void read2(long long &k) {
    k=0,hhd=getchar();
    while(hhd>'9'||hhd<'0') hhd=getchar();
    while(hhd<='9'&&hhd>='0') k=k*10+hhd-'0',hhd=getchar();
}
inline int get(int u) {
    if(fa[u]==u) return u;
    return fa[u]=get(fa[u]);
}
inline void dfs(int u) {
    f[u][1]=v[u];
    for(int i=a[u]; i; i=g[i].next) {
        int j=g[i].to;
        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=max(f[j][0],f[j][1]-g[i].v);
    }
}
inline void dfs1(int u,int k) {
    f[u][1]=v[u];
    for(int i=a[u]; i; i=g[i].next) {
        int j=g[i].to;
        dfs1(j,k);
        if(j==di[k]) {
            f[u][0]+=max(f[j][0],f[j][1]-zhi[k]);
            f[u][1]+=max(f[j][0],f[j][1]-g[i].v-zhi[k]);
            continue;
        }
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=max(f[j][0],f[j][1]-g[i].v);
    }
}
int main() {
    read1(n),read1(m);
    for(int i=1; i<=n; i++) read2(vv[i]),read1(xx[i]),read2(ji[i]);
    for(int k,i=1; i<=m; i++) {
        read1(zhu[++num]),read1(k),fa[i]=num;
        for(int kk,j=1; j<=k; j++) {
            read1(kk),fa1[kk]=i,v[i]+=vv[kk],mm[i].push_back(kk);
        }
    }
    for(int i=1; i<=n; i++) if(!fa1[i]) {
            zhu[++num]=i,fa1[i]=num,fa[num]=num;
            v[num]=vv[i],mm[num].push_back(i);
        }
    for(int i=1; i<=num; i++) {
        int res=0,y=fa1[xx[zhu[i]]];
        for(int j=0; j<mm[i].size(); j++) {
            int x=fa1[xx[mm[i][j]]];
            if(i==x) v[x]-=ji[mm[i][j]];
            else if(y==x) res+=ji[mm[i][j]];
        }
        if(i==y) continue;
        vi[i]=1;
        if(get(i)==get(y)) root[++top]=i,di[top]=y,zhi[top]=res;
        else {
            fa[fa[i]]=fa[y],g[++cnt].v=res,g[cnt].to=i;
            g[cnt].next=a[y],a[y]=cnt;
        }
    }
    for(int i=1; i<=num; i++) if(!vi[i]) dfs(i),ans+=max(f[i][1],f[i][0]);
    for(int kk=1; kk<=top; kk++) {
        long long asw=0;
        dfs1(root[kk],kk),asw=f[root[kk]][1],memset(f,0,sizeof(f));
        dfs(root[kk]),asw=max(asw,f[root[kk]][0]),ans+=asw;
    }
    printf("%lld",ans);
}