如题。在跑完 O(n3) 的 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[] (大写)表示当前匹配中左边的点 i 指向的右边的点编号,左右意义与原题相反。
才能得到 100pts,如果不做特判则会掉两个点。
用下面的代码也能通过。
rep(i,1,n) {
ans += w[L[i]][i];
}
wsm ? 求解答 qwq
附上一份代码:
https://gist.github.com/Patricky-Tau/741b4de2ac5df1a7f800878f468a5fca