UVa1407 Caves

UVa

Luogu

分析

设 $dp_{i,j,0/1}$ 表示以 $i$ 为根的子树,经过 $j$ 个点,最后不回到 / 回到 $i$ 的最小距离。

转移类似于树形背包,边界是 $dp_{i,1,0}=dp_{i,1,1}=0$ 。

询问的话就找到最大的使得 $\min\{dp_{1,i,0},dp_{1,i,1}\}\leq x$ 的 $i$ 就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
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-'0',c=getchar();
    return X*w;
}

const int N=500+10;

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

int n,Q;
int sz[N],dp[N][N][2],tmp[N][2];

inline void dfs(int u,int fa) {
    sz[u]=1,dp[u][1][0]=dp[u][1][1]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        dfs(v,u);
        memset(tmp,0x3f,sizeof(tmp));
        for (re int j=1;j<=sz[u];++j)
            tmp[j][0]=dp[u][j][0],tmp[j][1]=dp[u][j][1];
        for (re int j=1;j<=sz[u];++j)
            for (re int k=1;k<=sz[v];++k) {
                chkmin(tmp[j+k][0],dp[u][j][1]+dp[v][k][0]+w);
                chkmin(tmp[j+k][0],dp[u][j][0]+dp[v][k][1]+w+w);
                chkmin(tmp[j+k][1],dp[u][j][1]+dp[v][k][1]+w+w);
            }
        for (re int j=1;j<=sz[u]+sz[v];++j)
            dp[u][j][0]=tmp[j][0],dp[u][j][1]=tmp[j][1];
        sz[u]+=sz[v];
    }
}

int main() {
    int T=0;
    while (n=read()) {
        memset(head,0,sizeof(head)),cnt=0;
        for (re int i=1;i<n;++i) {
            int u=read()+1,v=read()+1,w=read();
            addEdge(v,u,w);
        }
        dfs(1,0);
        printf("Case %d:\n",++T);
        Q=read();
        while (Q--) {
            int x=read();
            for (re int i=n;i;--i)
                if (dp[1][i][0]<=x||dp[1][i][1]<=x) {
                    printf("%d\n",i); break;
                }
        }
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 45 PM

发表评论