题解：P5687 [CSP-S2019 江西] 网格图

HZY1618yzh · 2025-05-06 15:48:00 · 题解

题目传送门

题意

给定一个 n 行 m 列的网格图，每个格子是一个点。连接规则如下：

1. 横向边：第 i 行相邻的点之间有一条边，权值为 a_i。
2. 纵向边：第 j 列相邻的点之间有一条边，权值为 b_j。

要求：求出这个网格图的最小生成树（即用最少的边权总和连接所有点）。

解决方法

要求最少的边权总和连接所有点，所以需要贪心使得当前边权尽量小，因此需要排序。
不难证明，a 和 b 数组不管如何变化，最终都不影响最小生成树（改变那两个数组的顺序其实是交换了某两列/行的节点）。
注：后面讲解里，我们令权值越小的横向边（a）越靠上，权值越小纵向边（b）越靠左。当前没有填过数最小横向边标号为 i，纵向边为 j。
网格图一共有 nm 个节点，最小生成树需要 nm-1 条边。我们希望每一条边权值越小越好，可以考虑每次把最上面和最左边的那层节点放上边，因为那是当前纵横边里最小的 n-i+m-j 条边，减 i 和 j 是因为每层都会减少一条边。
不过这样这棵树，却变成了一层又一层的“厂”，并不联通。所以我们可以每层挑选 \min(a_i,b_i) 与外面的厂连接。

不过这是最优的贪心策略吗？大胆猜测，小心求证。如果 a=\{2,2,6,4\}，b=\{5,1000,2000,3400\} 的时候，很明显，选 a 的所有边和 b 的第一条边是最优策略，而我们的“厂字图”却不是最优的方案。
我们可以先确定 a_1 和 b_1 为基础边。接着选择剩下边里最小的 a_2，为了防止出现刚才不联通的情况，该边需要 n-2(i)-1 条。接着重复刚才的步骤，继续选择剩下边里最小，即可以得出刚才说的方案。

选择剩下边里最小可以用双指针实现，每个指针表示的是当前正在选第几条边（即 i 和 j）。比较当前最小值，可以求出最小的边。具体证明评论区讨论

语言代码：

• 输入。
• 对 a 和 b 数组排序。
• 取 a_1 和 b_1（最小的）作为基础边，增加给 ans。
• 然后利用双指针实现 ans 交替增加较小的 a_i、b_j 乘以剩余需要的边数。
• 输出答案。

具体实现

• c++

  #include<bits/stdc++.h>
  using namespace std;
  using ll = long long;
  int n,m,a[300001],b[300001];
  ll ans;
  int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)
      cin>>a[i];
  for(int i=1;i<=m;i++)
      cin>>b[i];
  //排序
  sort(a+1,a+n+1);
  sort(b+1,b+m+1);
  ans=(ll)a[1]*(m-1)+(ll)b[1]*(n-1);//取a_1和b_1（最小的）作为基础边
  int i=2,j=2;
  while(i<=n&&j<=m){
      if(a[i]<b[j]){//取较小的a_i或b_j
          ans+=(ll)a[i]*(m-j+1);//乘以剩余需要的边数
          i++;//移动指针
      }else{
          ans+=(ll)b[j]*(n-i+1);//乘以剩余需要的边数
          j++;//移动指针
      }
  }
  cout<<ans;
  return 0;
  }

• python

  n,m=map(int,input().split())
  a=list(map(int, input().split()))
  b=list(map(int, input().split())
  a.sort()
  b.sort()
  ans=a[0]*(m-1)+b[0]*(n-1)
  i,j=1,1
  while i<n and j<m:
  if a[i]<b[j]:
      ans+=a[i]*(m-j)
      i+=1
  else:
      ans+=b[j]*(n-i)
      j+=1
  print(ans)

  ~给个赞吧！~