P1364 医院设置

题目描述：P1364 医院设置

---

解题思路

---

• 解题思路

  1、由题意，无论取哪个点作根(医院)，都能够形成一棵树。首先，需要先整理这棵树，用邻接表建图记录这棵树的情况。注意：为了方便双向访问，应建立双向图
  2、对于树的总代价，可通过 BFS 一层一层向外遍历节点，标记节点 $i$ 的层数为 $dep[i]$，得到每个节点的代价 $w[i] * dep[i]$，将所有节点代价相加即为总代价
  3、由于数据范围较小，所以可以直接遍历整棵树，让每一个节点都作一次根跑一遍 BFS，取这些树中总代价最小的即为答案

---

代码实现

---

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 110, INF = 0x3f3f3f3f;
  
  vector<int> g[N]; // 建图记录树的情况
  int w[N], dep[N]; // 居民数 和 深度
  
  int BFS(int x)
  {
      int res = 0;   // 记录当前答案
      bitset<N> vis; // 标记是否访问过
  
      queue<int> q;
      q.push(x);
      dep[x] = 0;
      vis[x] = true;
  
      while (q.size())
      {
          int x = q.front();
          q.pop();
  
          for (int &y : g[x])
          {
              if (vis[y])
                  continue;
  
              dep[y] = dep[x] + 1;
              res += w[y] * dep[y];
              vis[y] = true;
              q.push(y);
          }
      }
  
      return res;
  }
  
  void solve()
  {
      int n;
      cin >> n;
      // 建立双向图
      for (int i = 1; i <= n; i++)
      {
          int u, v;
          cin >> w[i] >> u >> v;
          if (u)
              g[i].push_back(u), g[u].push_back(i);
          if (v)
              g[i].push_back(v), g[v].push_back(i);
      }
  
      // 遍历每个节点作根的情况，记录最小答案
      int ans = INF;
      for (int i = 1; i <= n; i++)
          ans = min(ans, BFS(i));
      cout << ans;
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---