P1364 医院设置（洛谷）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 //虽然此处是树状结构，其实也能用邻接表的方式进行bfs，分别以每个结点当起点进行bfs
 5 //建树方式也可以，只不过麻烦，bfs前还得建棵树 
 6 
 7 //新思路解决结点所在深度问题：设计一个结构体，保存当前结点的下标和深度，当前结点更新：上一层结点深度+1 
 8 int minn=1<<30;
 9 int n=0;
10 int mapp[105][105]={0};
11 bool v[105];        //用于判断某个点是否被访问过 
12 int w[105]={0};        //存人口数 
13 int bfs(int index){    //index下标,
14     memset(v,0,sizeof(v));
15     int sum=0;
16     int size=1;            //size表示的是当前层的结点数，每访问一个结点size--知道size减少到0代表当前层的结点全部已经遍历，此时深度step++ 
17                         //因为只有遍历完当前层最右边的点后深度step才会加1，同时也才进入下一层 
18     int temp=0;            //temp记录的是当前层的下一层的结点数,当size为0的时候，意味着进入下一层去遍历，
19                         // 因此temp值赋给size,而temp情况重新累计下一层的结点数 
20     queue<int> q;
21     q.push(index);        //起点入队
22     v[index]=1; 
23     int step=1;            //记录bfs搜索层数 
24     while(!q.empty()){ 
25         int cur=q.front();        //cur是当前结点下标 
26         q.pop();
27         for(int i=1;i<=n;i++){
28             if(mapp[cur][i]==0||v[i])    continue;
29             sum+=w[i]*step;
30             q.push(i);        //入队
31             v[i]=1; 
32             
33             if(size>0){
34                 temp++;
35             }
36         }
37         size--;
38         if(size==0){
39             size=temp;
40             temp=0;            //又重新清0 
41             step++;
42         }
43     }
44     return sum;
45 } 
46 int main(){
47     cin>>n;
48     for(int i=1;i<=n;i++){
49         int v,u;
50         cin>>w[i];
51         cin>>u>>v;
52         
53         //再输入0的情况下也标了1 
54         if(u) mapp[i][u]=1;    //表示有连接 
55         if(u) mapp[u][i]=1;    //无向图 所以对称
56         if(v) mapp[i][v]=1;
57         if(v) mapp[v][i]=1;
58     }
59 
60     for(int i=1;i<=n;i++){    //设每次bfs的起点是医院位置         
61         minn=min(minn,bfs(i));
62     }
63     cout<<minn;
64     return 0;
65 }