关于 树形dp 的复杂度分析

__Watcher @ 2020-08-28 14:28:44

int dfs(int u, int fa) {
    int now=1;
    f[u][0]=f[u][1]=0;
    for(int k=h[u];k;k=d[k].n) {
        int v=d[k].b, c=d[k].c;
        if(v==fa) continue;
        int tmp=dfs(v, u);
        for(int i=min(now+tmp,m);i>=2;i--) {
            for(int j=min(now,i);j>=1;j--) {
                cnt++;
                f[u][i]=min(f[u][i], f[u][j]+f[v][i-j]+c*(i-j)*(m-i+j));
            }
        }
        now+=tmp;
    }
    return now;
}

by __Watcher @ 2020-08-28 14:29:20

以下是完整程序：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read() {
    ll x=0, f=1; char ch=' ';
    while(!isdigit(ch)) {ch=getchar(); if(ch=='-') f=-1;}
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return x*f;
}
int n, m, tot, h[1505], cnt;
int f[1505][1005];
struct AB{
    int a, b, c, n;
}d[3005];
void charu(int a, int b, int c) {
    d[++tot].a=a, d[tot].b=b, d[tot].c=c, d[tot].n=h[a], h[a]=tot;
}
int dfs(int u, int fa) {
    int now=1;
    f[u][0]=f[u][1]=0;
    for(int k=h[u];k;k=d[k].n) {
        int v=d[k].b, c=d[k].c;
        if(v==fa) continue;
        int tmp=dfs(v, u);
        for(int i=min(now+tmp,m);i>=2;i--) {
            for(int j=min(now,i);j>=1;j--) {
                cnt++;
                f[u][i]=min(f[u][i], f[u][j]+f[v][i-j]+c*(i-j)*(m-i+j));
            }
        }
        now+=tmp;
    }
    return now;
}
int main() {
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        int a=read(), b=read(), c=read();
        charu(a, b, c);
        charu(b, a, c);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            f[i][j]=1e9;
        }
    }
    dfs(1, 1);
    printf("%.2lf", (double)f[1][m]/(m*(m-1)/2));
    cout<<endl<<cnt;
}

by c2020HXW @ 2020-08-28 14:32:08

这应该是O(nm^2)的吧

by LuoShaoyinn @ 2020-08-28 14:34:16

代码上看并不是O(mn)....

by t162 @ 2020-08-28 14:35:18

好像这个代码不是 \operatorname O(nm)...

by wgyhm @ 2020-08-28 14:35:21

同楼上的楼上

by wgyhm @ 2020-08-28 14:35:52

最坏应该是 O(nm^2)

by __Watcher @ 2020-08-28 14:37:10

@违规用户名FkZyA0!2 @Anticyclone 网上的复杂度证明

by __Watcher @ 2020-08-28 14:37:58

@Anticyclone 菊花图肯定不会 T 啊

by __Watcher @ 2020-08-28 14:38:33

@142857cs 求一求怎么改？

by Effulgent @ 2020-08-28 14:38:36

for(int i=min(now+tmp,m);i>=2;i--) {
            for(int j=min(now,i);j>=1;j--) {
                cnt++;
                f[u][i]=min(f[u][i], f[u][j]+f[v][i-j]+c*(i-j)*(m-i+j));
            }
        }

第二个循环处上界需要是v子树的size，复杂度才是nm。