P1229医院设置 题解

· · 个人记录

更好的阅读体验

心路历程

一开始看了看题面就自闭了很久（带权树的重心？）

后来惊奇地发现数据范围只有100?!!

那还想什么？暴力啊！！！

解法

对于每一个点，都有一个权值、父节点、左儿子和右儿子（没有的是0）

于是就有：

struct node
{
    int w,fa,l,r;
}a[110];

然后思路是：

对于每一个节点，跑一遍DFS，求出距离和，然后取最小值。

于是：

int main()
{
    //输入
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].w>>a[i].l>>a[i].r;
        a[a[i].l].fa=i,a[a[i].r].fa=i;
    }
    //求最小值
    //dfs( now（当前节点）, last（上一个节点), dis（当前距离）)
    int minn=2147483647;
    for(int i=1;i<=n;i++)
        minn=min(minn,dfs(i,0,0));
    //输出
    cout<<minn<<endl;
    //完结撒花！！！
    return 0;
}

dfs:

int dfs(int now,int last,int dis)
{
    //特判
    if(now==0)
        return 0;
    //加入自身
    int ans=dis*a[now].w;
    //if避免出现死循环
    if(a[now].fa!=last)
        ans+=dfs(a[now].fa,now,dis+1);
    if(a[now].l!=last)
        ans+=dfs(a[now].l,now,dis+1);
    if(a[now].r!=last)
        ans+=dfs(a[now].r,now,dis+1);
    //返回
    return ans;
}

完整代码 （知道你们就是来看这个的）：

#include<iostream>
using namespace std;
struct node
{
    int w,fa,l,r;
}a[110];
int dfs(int now,int last,int dis)
{
    if(now==0)
        return 0;
    int ans=dis*a[now].w;
    if(a[now].fa!=last)
        ans+=dfs(a[now].fa,now,dis+1);
    if(a[now].l!=last)
        ans+=dfs(a[now].l,now,dis+1);
    if(a[now].r!=last)
        ans+=dfs(a[now].r,now,dis+1);
    return ans;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].w>>a[i].l>>a[i].r;
        a[a[i].l].fa=i,a[a[i].r].fa=i;
    }
    int minn=2147483647;
    for(int i=1;i<=n;i++)
        minn=min(minn,dfs(i,0,0));
    cout<<minn<<endl;
    return 0;
}