关于一个很有用的基本模型的问题
  • 板块学术版
  • 楼主Madefaker
  • 当前回复17
  • 已保存回复17
  • 发布时间2021/10/12 15:04
  • 上次更新2023/11/4 04:00:09
查看原帖
关于一个很有用的基本模型的问题
464632
Madefaker楼主2021/10/12 15:04

aa 数组和 bb 数组都有 nn 个数,并且它们都是 nn 的排列。若每次可以交换 aa 中任意的两个数,求将 aa 变成 bb 的最小交换次数。

例如 a=[4,2,3,1],b=[1,2,3,4]a = [4,2,3,1],b = [1,2,3,4],将 a0=4a_0=4a3=1a_3 = 1 交换,得到 bb 数组。于是最小交换次数为 11

这个基本模型的一个通用解法是:建立一张 nn 个点的图,对于 oin1o \le i \le n - 1,建立无向边 ai,bia_i,b_i。那么最小交换次数就是 ncn-c,其中 cc 表示这个图中连通块的个数。

哪位大佬可以给出这个解法的解释与证明?谢谢!

2021/10/12 15:04
加载中...