二分图最大权完美匹配
NTG_Adiord · · 题解
2023/2/12部分
不是很想看正经题解，来点大白话题解
本文默认你已经学习过了dfs版本的km算法并且来做这道题
简单说明一下bfs(queue)版本的逻辑
slack(loss)-pre 记录如果选择该(右侧)点，最小的损失/最大的收益是多少(显然正的是损失负的是增益)，pre记录造成该增益/损失的点是哪个点
初始的时候把想匹配的点扔队列里,拿他对右侧点集中的每一个点更新slack，如果能把slack更新，就把被更新右侧点的pre改成该左侧点(我写的loss，生动形象)
然后从右侧取出损失最小/增益最大的点的d
之后是km的标准操作，本轮可被选中的右侧点的slack(loss)会变成0
操作完了之后从右侧找本轮还没匹配的点(特征是visy!=0),并且slack(loss)为0的点
然后分两种情况，如果linkY(右侧点连接了左侧的谁)为0,说明没匹配，直接重新匹配return就完了
如果不为0,说明这个点可以拿出来匹配了，但是他已经配对过了，就把他对应的linkY抓出来扔queue里，然后就是转回去重新跑queue了(如果没碰见linkY=0的话)
那这为什么是BFS呢
其实就是，我要从起点开始匹配了，我更新slack(loss),我要取slack(loss)最小的值开始匹配，我抓了一大堆都是loss最小的点，要是这里有没被匹配的，正好直接抓去更新就完事，要是全被匹配了，把其对应的左侧点都扔queue里，这些点再匹配的损失都是相同的,然后再继续重新跑slack(loss)的更新直到出现没被匹配过的点
关于最后是怎么重分配的
逻辑上是起点->一堆被踢掉的等价点->一堆被踢掉的等价点->没被分配的终点
终点(右侧点)的pre是一个左侧点,记终点为v,先记是pre[v]原来匹配的点为prev,然后把pre[v]和v互相匹配，然后再抓prev继续更新就行了(有人想和prev进行匹配，prev有了一个新的pre,然后请求其匹配点(pre[v])去重新匹配,顺着就能找回到最初要匹配的点，理解一下)
详情参考代码,后续会补充一下迭代bfs的个人理解
#include <bits/stdc++.h>
#define ll long long
#define inf 1000000000000000
using namespace std;
int n, m;
ll val[501][501];
ll valx[501],valy[501],visx[501],visy[501],loss[501],pre[501];
ll linkX[501];
ll linkY[501];
queue<int> que;
void inpu(){
scanf("%d%d", &n, &m);
/*初始化边权为负最大*/
for (int i = 1; i <= 500;i++){
for (int j = 1; j <= 500;j++){
val[i][j] = -inf;
}
}
/*读入*/
for (int i = 1; i <= m; i++)
{
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
val[u][v] = max(val[u][v], w);
}
}
void KM(int st){
/*重置访问过的点,以及设置loss为inf*/
for (int i = 1; i <= 500;i++)visx[i] = visy[i] = 0,loss[i]=inf;
while(!que.empty())que.pop();
que.push(st);
while(1){
/*把队列中的点抓出来更新其他点的loss*/
while(!que.empty()){
int u = que.front();
que.pop();
visx[u] = 1;
for (int v = 1; v <= n;v++){
ll newloss = valx[u] + valy[v] - val[u][v];
if(visy[v]||newloss>loss[v])continue;//走过的点和不能更新的点跳过
loss[v] = newloss;
pre[v] = u;
}
}
/*找到最小的loss*/
ll d = inf;
for (int i = 1; i <= n;i++)if(!visy[i])d = min(d, loss[i]);
for (int i = 1; i <= n;i++){
/*标准操作，如果是未被选中的右侧点,原来的式子是visx+visy-val[x][y]=loss,应该更新一下减去d*/
if(visx[i])valx[i] -= d;
if(visy[i])valy[i] += d;
else loss[i] -= d;
}
for (int i = 1; i <= n;i++){
if(visy[i]||loss[i]!=0)continue;//已经走过的点和非当前最优点跳过
if(!linkY[i])/*重分配*/{
int v = i;
while(v){
int prev = linkX[pre[v]];
linkY[v] = pre[v];
linkX[pre[v]] = v;
v = prev;
}
return;
}
visy[i] = 1;
que.push(linkY[i]);
}
}
}
int main(){
inpu();
for (int i = 1;i<=n;i++){
KM(i);
}
ll ans = 0;
for (int i = 1; i <= n;i++)
ans += valx[i] + valy[i];
printf("%lld\n", ans);
for (int i = 1; i <= n;i++){
printf("%lld ", linkY[i]);
}
}2023/2/13部分
queue
整理结合了两位大佬的代码，remake后的queue版本bfs
把初始节点和右侧虚点0相连，能形成一个有v必有u的结构，就不用记录linkX,visX了，linkY就能找到对应的v-u关系,pre只要记录上一个右侧点是谁就行
加了个ed,表示找到的终点，最后统一处理
同时把代码压到了67行，可喜可贺
#include <bits/stdc++.h>
#define ll long long
#define inf 1000000000000000
using namespace std;
int n, m;
ll val[501][501];
ll valx[501],valy[501],visy[501],loss[501],pre[501];
ll linkY[501];
queue<int> que;
void inpu(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= 500;i++){
for (int j = 1; j <= 500;j++){
val[i][j] = -inf;
}
}
for (int i = 1; i <= m; i++){
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
val[u][v] = max(val[u][v], w);
}
}
void KM(int st){
for (int j = 1; j <= 500;j++)visy[j] = 0,loss[j]=inf;
while(!que.empty())que.pop();
que.push(0);
visy[0] = 1;
linkY[0] = st;
int ed = 0;
while(!ed){
while(!que.empty()){
int v = que.front();que.pop();
int u = linkY[v];
for (int vt = 1; vt <= n;vt++){
ll newloss = valx[u] + valy[vt] - val[u][vt];
if(visy[vt]||newloss>=loss[vt])continue;
loss[vt] = newloss;
pre[vt] = v;
}
}
ll d = inf;
for (int vt = 1; vt <= n;vt++)if(!visy[vt])d = min(d, loss[vt]);
for (int vt = 0; vt <= n;vt++){
if(visy[vt])valx[linkY[vt]] -= d,valy[vt]+=d;
else loss[vt] -= d;
}
for (int vt = 1; vt <= n;vt++){
if(visy[vt]||loss[vt]!=0)continue;
if(!linkY[vt]) ed = vt;
visy[vt] = 1;
que.push(vt);
}
}
while(ed){
linkY[ed] = linkY[pre[ed]];
ed = pre[ed];
}
}
int main(){
inpu();
for (int i = 1;i<=n;i++)KM(i);
ll ans = 0;
for (int i = 1; i <= n;i++)
ans += val[linkY[i]][i];
printf("%lld\n", ans);
for (int i = 1; i <= n;i++)printf("%lld ", linkY[i]);
}迭代
迭代的思想大概就是,从起点开始,抓这个起点去更新右侧点的loss和pre,每次只从loss最小的那层上抓一个点出来，如果其未被连接就进行重新配对，如果已经被连接了就抓去更新(que版本的其实就是把整层最小点全抓出来更新)
详情见以下代码
#include <bits/stdc++.h>
#define ll long long
#define inf 10000000000000000
using namespace std;
int n, m;
ll val[501][501];
ll valx[501],valy[501],visy[501],loss[501],pre[501];
ll linkY[501];
void ot(){
ll ans = 0;
for (int i = 1; i <= n;i++)
ans += valx[i] + valy[i];
printf("%lld\n", ans);
for (int i = 1; i <= n;i++){
printf("%lld ", linkY[i]);
}
}
void inpu(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= 500;i++){
for (int j = 1; j <= 500;j++){
val[i][j] = -inf;
}
}
for (int i = 1; i <= m; i++){
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
val[u][v] = max(val[u][v], w);
}
}
void KM(int st){
for (int i = 1; i <= 500;i++)visy[i] = pre[i]=0,loss[i]=inf;
linkY[0] = st;
int v = 0, lv = 0;
while(linkY[v]){
int u = linkY[v];visy[v] = 1;//抓这个点来更新
for (int vt = 1; vt <= n;vt++){
ll newloss = valx[u] + valy[vt] - val[u][vt];
if(visy[vt]||loss[vt]<=newloss)continue;
loss[vt] = newloss;
pre[vt] = v;//如果vt被选中了，他的上一个右侧点是v
}
ll d = inf;
for (int i = 1; i <= n;i++)if(!visy[i]&&loss[i]<d)//找到其中一个loss最小的点
d = loss[i], lv = i;
for (int i = 0; i <= n;i++){
if(visy[i])valx[linkY[i]]-=d,valy[i] += d;
else loss[i] -= d;
}
v = lv;//把loss最小点抓出来
}//如果被抓出来的点没有对应的左侧节点就到下面重匹配
while(v){
linkY[v] = linkY[pre[v]];
v = pre[v];
}
}
int main(){
inpu();
for (int i = 1;i<=n;i++){
KM(i);
}
ot();
}