M_sea

洛谷1273 有线电视网
Luogu分析设$f[i][j]$表示以i为根的子树,选j个用户的最大价值。然后就是个树上的分组背包。代码#inc...
扫描右侧二维码阅读全文
01
2018/11

洛谷1273 有线电视网

Luogu

分析

设$f[i][j]$表示以i为根的子树,选j个用户的最大价值。

然后就是个树上的分组背包。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline void chmax(int& a,int b) { if (b>a) a=b ; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-48,c=getchar();
    return X*w;
}

const int MAXN=3010;

struct Edge { int v,w,nxt; };
Edge e[MAXN];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v,e[cnt].w=w;
    e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m;
int val[MAXN];

int f[MAXN][MAXN]; //f[i][j]表示以i为根的子树,选j个用户的最大值 

inline int Dfs(int u) {
    if (u>n-m) { f[u][1]=val[u]; return 1; }
    int rt=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w,sz=Dfs(v); rt+=sz;
        for (re int i=rt;i>0;--i)
            for (re int j=1;j<=sz;++j)
                if (i>=j) chmax(f[u][i],f[u][i-j]+f[v][j]-w);
    }
    return rt;
}

int main() {
    memset(f,192,sizeof(f));
    n=read(),m=read();
    for (re int i=1;i<=n-m;++i) {
        int k=read();
        for (re int j=1;j<=k;++j) {
            int v=read(),w=read();
            addEdge(i,v,w);
        }
    }
    for (re int i=n-m+1;i<=n;++i) val[i]=read();
    for (re int i=1;i<=n;i++) f[i][0]=0;
    Dfs(1);
    for (re int i=m;i>=1;--i)
        if (f[1][i]>=0) {
            printf("%d\n",i);
            break;
        }
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 19 PM

发表评论