[LUOGU] 1364 医院设置

设有一棵二叉树，如图：

 【我是图】

其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1。如上图中，

若医院建在1 处，则距离和=4+12+2*20+2*40=136；若医院建在3 处，则距离和=4*2+13+20+40=81……

输入输出格式

输入格式：

第一行一个整数n，表示树的结点数。(n≤100)

接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格(一个或多个)分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。

输出格式：

一个整数，表示最小距离和。

输入输出样例

输入样例#1： 复制

5

13 2 3

4 0 0

12 4 5

20 0 0

40 0 0

输出样例#1： 复制

81

以每个节点为医院，枚举距离。(floyd?)

顺带邻接表。

//Writer:GhostCai && His Yellow Duck

#include<iostream>

#include<cstring>

#define MAXN 2000

using namespace std;

//

struct edge{

    int to,next;

}e[MAXN];

int cnt,head[MAXN];

void add(int x,int y){

    e[++cnt].to = y;

    e[cnt].next = head[x];

    head[x]=cnt;

}

//

int n,ans=1<<30;

int dis[MAXN],num[MAXN];

bool vis[MAXN];

void dfs(int id,int dp){

    int i;

    for(i=head[id];i!=-1;i=e[i].next){

        if(!e[i].to || vis[e[i].to ]) continue;

        vis[e[i].to ]=1;

        dis[e[i].to] = dp+1;

        dfs(e[i].to , dp+1);

    }

}

int main(){

    cin>>n;

    int i,j,x,y;

    memset(head,-1,sizeof(head));

    for(i=1;i<=n;i++){

        cin>>num[i]>>x>>y;

        add(i,x);add(x,i);

        add(i,y);add(y,i);

    }

    for(i=1;i<=n;i++){

        memset(dis,0,sizeof(dis));

        memset(vis,0,sizeof(vis));

        vis[i]=1;//!!!

        dfs(i,0);

        int sum=0;

        for(j=1;j<=n;j++){

            sum+=num[j]*dis[j];

        }

        ans=min(sum,ans);

    }

    cout<<ans<<endl;

    return 0;

}