P11862「o.OI R1」Easy ver.

Joushi_Ikita · 2025-03-09 21:11:08 · 题解

乍一看被吓到了（雾）

正文开始

一、题意：

对于一个 n \times m 的矩阵，其中填有 1 到 n \times m 的 n \times m 个整数， 相邻两个整数之间有一条边，边权为两数中的较大值（如下）。

求使最小生成树边权和最小的一种方案（上述情况为 2 \times 3 时的一种解，最小生成树如下（不只一种），边权和为 20）。

二、分析：

一般人乍一看应该会和我一样以为要用一些高级的算法或数据结构。
首先考虑到最小生成树的算法之一——Kruskal 的核心思想为贪心，我们可以尝试贪心地去思考问题。
在 Kruskal 中，我们每次都用最短的一条边来将两个点集连接起来，在这个问题中，我们可以将其简化，每次都将一个新的点连到已有的点集上（特别的，点集初始为点 1），易得这条边的边权最小为这个新点的点权。
为使取到这个最小值，这个新点应接到点集中一个点权比它小的点上（这也是为什么点集初始为点 1），不考虑矩阵的结构，连成一条链是最简单的方案（如下）。
1<-->2<-->3<-->4<-->5<-->6
把它放回到矩阵里，就是一个蛇形填数的矩阵（如下（带划掉的是不在链中的边））。

于是，这题就变成一道简单的蛇形填数了！
代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i%2){
                cout<<j+(i-1)*m<<' ';
            }
            else cout<<i*m-j+1<<' ';
        }
        cout<<endl;
    }
    return 0;
}

你以为这就完了？别急，还有优化。

三、优化：

观察到蛇形填数还不够简洁，思考普通填数可否解决。

观察如上矩阵，发现每行自身满足链状结构，达到局部最优，而将每行第一个数接到上一行第一个数上，依旧满足之前所述的贪心结论，方案可行。
于是我们就得到了最简方案。

四、最终代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
                cout<<j+(i-1)*m<<' ';
        }
        cout<<endl;
    }
    return 0;
}