题解 P1875 【佳佳的魔法药水】

· · 题解

强烈建议管理员改标签！！！

相信大多数人都是看见最短路才点进来的。

我也是这样。

但是这题应该是一个树形DP。

为什么这么说呢？

这里给出的配方关系，其实是一棵树。

因为不可能A需要B，B又需要A，那就生产不出来了。

那么设f[i]为第i种药的最小值，

sz[i]为第i种最小值的方案数。

每次枚举它的一种配方a,b，

如果这种配方更优，就更新答案，

如果跟以前一样优，就更新数量。

if(f[a]+f[b]<f[i]){
   f[i]=f[a]+f[b];
   sz[i]=sz[a]*sz[b];
}else if(f[a]+f[b]==f[i]){
   sz[i]+=sz[a]*sz[b];
}

稍微提一下，如果存边觉得vector套pair太慢的话，

可以像我这样，用链式前向星来存。

还有一点，输出要放在递归函数里面，不然玄学WA。

时间复杂度O(n)

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
const int maxm=1000000;
int n,f[maxn],sz[maxn],vis[maxn];
int beg[maxm],nex[maxm],a[maxm],b[maxm],e;
inline void add(int x,int y,int z){
    e++;nex[e]=beg[z];
    beg[z]=e;a[e]=x;b[e]=y;
}
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*f;
}
inline int dfs(int x){
    //printf("%d\n",x);
    if(vis[x])return f[x];
    vis[x]=1;
    for(int i=beg[x];i;i=nex[i]){
        int p=dfs(a[i]),q=dfs(b[i]);
        //printf("%d %d %d\n%d %d %d\n",a[i],p,sz[a[i]],b[i],q,sz[b[i]]);
        if(p+q==f[x])sz[x]+=sz[a[i]]*sz[b[i]];
        if(p+q<f[x]){
            f[x]=p+q;
            sz[x]=sz[a[i]]*sz[b[i]];
        }
        //printf("%d %d %d %d\n",f[x],p,q,sz[x]);
    }
    if(x==0)printf("%d %d\n",f[x],sz[x]);
    return f[x];
}
int main(){
    n=read();
    for(int i=0;i<n;i++){
        f[i]=read();
        sz[i]=1;
    }
    int x,y,z;
    while(scanf("%d%d%d",&x,&y,&z)!=EOF)add(x,y,z);
    dfs(0);
    return 0;
}