题解 P1364 【医院设置】

雪风舞者 · 2017-10-23 21:16:34 · 题解

第一次写题解好激动(≧▽≦)/

好了不多说了

下面的题解区代码好多_floyd_的……

那我就写个别的好了O(∩_∩)O~

思路

用普通图的形式存储，

进行n遍bfs，然后每遍都进行答案的比较更新

时间复杂度

由于bfs每遍都是O(V+E)的，而这里特殊之处在于本身是个树，所以是n个节点和n-1条边

所以总复杂度近似为O(n^2)，完美解决

——————————————————————————朴实的分割线——————————————————————————————

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
bool g[105][105]={0};            //这里n小我就直接邻接矩阵了，如果用邻接表还能快点 
bool v[105]={0};
int n,num[105],ans=1<<30;
struct node{
    int u,step;
};
int bfs(int x){                    //bfs找当前点x为医院设置点时的总距离 
    memset(v,0,sizeof(v));
    queue<node> q;
    v[x]=1;
    q.push((node){x,0});
    int sum=0;
    while(!q.empty()){
        node now=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
            if(g[now.u][i]&&!v[i]){
                node next={i,now.step+1};
                sum+=num[i]*next.step;
                v[i]=1;
                q.push(next);
            }
    }
    return sum;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int a,l,r;
        scanf("%d%d%d",&a,&l,&r);
        num[i]=a;
        if(l) g[i][l]=g[l][i]=1;
        if(r) g[i][r]=g[r][i]=1;
    }
    for(int i=1;i<=n;i++)
        ans=min(ans,bfs(i));
    printf("%d",ans);
    return 0;
}