洛谷传送门

思路

可以将每个位置看成点，交换操作看成边。

那么为了排序，每个数的当前位置与目标位置必须是连通的。

我们可以由大到小不断增加边，并检查 $N$ 对点之间的连通性，但这样做效率较低。

不难发现，⼀旦对点连通后，增加更多的边不会改变连通性。

所以可以直接⼆分答案求解。

确定了最小代价后，再根据可用的边求图中的连通块，最后再统一进行判定。

时空复杂度

令代价的取值范围为 $v$ 。

时间：

• 二分答案 $\Theta(\log v)$
• 求连通块 $\Theta(N + M)$
• 校验答案 $\Theta(N)$

总共 $\Theta((N + M) \log v)$

空间：

储存图 $\Theta(N + M)$

$code$

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int kMaxN = 1e5 + 1;

struct E {   // 边
  int y, w;  // 指向节点，宽度
};

struct V {
  int r;  // 所属连通块标记
  vector<E> p;
} v[kMaxN];

int a[kMaxN];
int n, m, x, y, w, l, r, _r, mid;

void T(int r, int x) {  // x属于连通块r
  if (v[x].r) {         // 已经到达过x
    return;
  }
  v[x].r = r;                                // 标记
  for (int i = 0; i < v[x].p.size(); i++) {  // 寻找邻点
    if (v[x].p[i].w >= mid) {                // 可以通行
      T(r, v[x].p[i].y);
    }
  }
}

bool C() {
  for (int i = 1; i <= n; i++) {  // 初始化连通块标记
    v[i].r = 0;
  }
  for (int i = 1; i <= n; i++) {
    if (!v[i].r) {  // 尚未查找的连通块
      T(i, i);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (v[i].r != v[a[i]].r) {  // 与要交换的位置不连通
      return 0;
    }
  }
  return 1;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> x >> y >> w;
    v[x].p.push_back({y, w});
    v[y].p.push_back({x, w});
    _r = max(_r, w);  // 跟新上界
  }
  for (l = 1, r = ++_r; l <= r;) {  // 二分答案，上界+1用来判无解
    mid = (l + r) >> 1;
    if (C()) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << (l > _r ? -1 : l - 1);
  return 0;
}