题目链接:
题目大意:二分图匹配费用流。①最大匹配②最小原配变动
解题思路:
如果去掉第二个要求,那么就是裸KM。
然而加上第二个要求,那么就需要一种新的建图方式。
建图
对于输入矩阵,每一条边,cost扩大K倍($K=n+1$)
对于原配,每一条边cost在扩大K倍基础上+1
KM
统计cost时,直接把cost整除K,然后累加。
并且Hash一下原配边的变动情况。
扩大K倍的作用
准确来说,K倍是为了+1而存在的。由于要优先考虑原配边,所以cost要大些。
但是,加大的cost又要使得最后好统计真实的cost。所以选择扩大K倍,然后整除K,这样,+1会被直接舍掉。
K=n+1是防止n=1的情况被卡姿势。
代码
#include "iostream"#include "cstdio"#include "cstring"#include "algorithm"using namespace std;#define maxn 55int n,m,Hash[maxn],tmp,old,K;int link[maxn],LX[maxn],RX[maxn],W[maxn][maxn],slack[maxn],e[maxn][maxn];bool S[maxn],T[maxn];const int inf=0x3f3f3f3f;bool dfs(int u){ S[u]=true; for(int v=1;v<=m;v++) { if(T[v]) continue; int t=LX[u]+RX[v]-W[u][v]; if(!t) { T[v]=true; if(!link[v]||dfs(link[v])) { link[v]=u; return true; } } else if(t