wustoj(医院设置)

朴灿烈づ我的快乐病毒、 2022-06-05 05:40 134阅读 0赞

问题描述:

一颗二叉树有n（1≤n≤50）个结点，分别编号为1到n，每个结点代表一个居民点，每个居民点都有一定数量的居民（≤100）。现在需要选择一个居民点建一家医院，使得所有居民走的路程之和最小。同时约定，相邻两节点之间的距离为1。

例如对于样例，有5个居民点，每个居民点的居民数量分别为13，4，12，20，40.如果选择居民点1作为医院位置的话，则距离和为4\*1+13\*0+12\*1+20\*2+40\*2=136；若选择居民点3的话，则距离和为4\*2+13\*1+12\*0+20\*1+40\*1=81，…

Input

包含多组测试数据。每组测试数据第一行包含一个整数n，接下来的n行，每行3个数据，表示居民点i（1≤i≤n）的居民数和相邻两个居民点编号，如果编号为0表示不存在。

Output

输出最小距离和。

sample input

5  
13 2 3  
4 0 0  
12 4 5  
20 0 0  
40 0 0

sample output

题目分析:我们不用把这个树构造出来，只需要保存每个节点的儿子，注意这个是一棵无向树，对称的。然后我们把每个节点当作医院去dfs

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    using namespace std;
    
    vector<int> vec[55];
    int v[55],res,n;
    bool vis[55];
    bool check()
    {
        for (int i=1;i<=n;i++)
            if (!vis[i]) return false;
        return true;
    }
    void dfs(int cur,int step)
    {
        for (int i=0;i<vec[cur].size();i++) {
            if (!vis[vec[cur][i]]) {
                vis[vec[cur][i]]=true;
                res+=step*v[vec[cur][i]];
                dfs(vec[cur][i],step+1);
            }
        }
    }
    int main()
    {
        while (scanf("%d",&n)!=EOF) {
            for (int i=1;i<=n;i++) {
                int a,b;
                scanf("%d%d%d",&v[i],&a,&b);
                if (a!=0) {
                    vec[i].push_back(a);
                    vec[a].push_back(i);
                }
                if (b!=0) {
                    vec[i].push_back(b);
                    vec[b].push_back(i);
                }
            }
            int ans=0x3f3f3f3f;
            for (int i=1;i<=n;i++) {
                memset (vis,false,sizeof (vis));
                vis[i]=true;res=0;
                dfs(i,1);
                if (check())
                   ans=min(res,ans);
            }
            printf("%d\n",ans);
            for (int i=1;i<=n;i++)
                vec[i].clear();
        }
        return 0;
    }