关于边权为 -N*M 的特判
查看原帖
关于边权为 -N*M 的特判
411103
Patricky楼主2022/8/7 21:01

如题。在跑完 O(n3)\mathcal O(n^3) 的 KM 之后统计答案时,使用如下代码:

rep(i,1,n) {
  ans += l[i] + r[i];
  if (w[L[i]][i] == -1LL * n * m) {
    ans -= -1LL * n * m;
  }
}

其中 l[], r[] 分别表示给两部各点分配的势,w[][] 存边权,L[] (大写)表示当前匹配中左边的点 ii 指向的右边的点编号,左右意义与原题相反。

才能得到 100pts,如果不做特判则会掉两个点。

用下面的代码也能通过。

rep(i,1,n) {
  ans += w[L[i]][i];
}

wsm ? 求解答 qwq

附上一份代码:

https://gist.github.com/Patricky-Tau/741b4de2ac5df1a7f800878f468a5fca

2022/8/7 21:01
加载中...