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

浪贱圣 · 2018-07-26 12:48:32 · 题解

研究样例发现是一棵树，所以我们可以直接建树，然后dfs就可以求出答案 上代码

#include<iostream>
using namespace std;
int cnt,h[1005],n,ans[1005],g[1005];
bool f[1005];
struct d{
    int x,y,next;
}a[10000005];
void add(int xx,int yy,int zz){
    ++cnt;
    a[cnt].x=xx;
    a[cnt].y=yy;
    a[cnt].next=h[zz];
    h[zz]=cnt;
}//建立邻接表 
void dfs(int u){
    f[u]=true;
    for(int i=h[u];i;i=a[i].next){
        if(!f[a[i].x])dfs(a[i].x);
        if(!f[a[i].y])dfs(a[i].y);
        if(ans[a[i].x]+ans[a[i].y]<ans[u]){
            ans[u]=ans[a[i].x]+ans[a[i].y];
            g[u]=g[a[i].x]*g[a[i].y];
        }//更新答案 
        else if(ans[a[i].x]+ans[a[i].y]==ans[u]){
            g[u]+=g[a[i].x]*g[a[i].y];
        }//更新答案 
    }
}
int main(){
    cin>>n;
    int xx,yy,zz;
    for(int i=0;i<n;++i){
        cin>>ans[i];
        g[i]=1;
    }
    while(cin>>xx>>yy>>zz){
        add(xx,yy,zz);
    }
    dfs(0);
    cout<<ans[0]<<' '<<g[0];
    return 0;
}