題意：求最大權(quán)匹配，要求改動(dòng)最少。。。。做法很巧妙，現(xiàn)在原權(quán)值乘上一個(gè)很大的倍數(shù)，比如100，然后再加上一個(gè)小量，加上小量以后對(duì)匹配出來的結(jié)果沒有影響，但可以求解出改動(dòng)最小。。。

#include <iostream> #include <queue> #include <stack> #include <map> #include <set> #include <bitset> #include <cstdio> #include <algorithm> #include <cstring> #include <climits> #include <cstdlib> #include <cmath> #include <time.h> #define maxn 55 #define maxm 400005 #define eps 1e-10 #define mod 1000000007 #define INF 999999999 #define PI (acos(-1.0)) #define lowbit(x) (x&(-x)) #define mp make_pair #define ls o<<1 #define rs o<<1 | 1 #define lson o<<1, L, mid #define rson o<<1 | 1, mid+1, R #define pii pair<int, int> #pragma comment(linker, "/STACK:16777216") typedef long long LL; typedef unsigned long long ULL; //typedef int LL; using namespace std; LL qpow(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base;base=base*base;b/=2;}return res;} LL powmod(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base%mod;base=base*base%mod;b/=2;}return res;} // headint g[maxn][maxn]; int linker[maxn]; int slack[maxn]; bool visx[maxn]; bool visy[maxn]; int lx[maxn]; int ly[maxn]; int n, m, nx, ny, init;bool dfs(int x) {visx[x] = true;for(int y = 0; y < ny; y++) {if(visy[y]) continue;int tmp = lx[x] + ly[y] - g[x][y];if(!tmp) {visy[y] = true;if(linker[y] == -1 || dfs(linker[y])) {linker[y] = x;return true;}}else slack[y] = min(slack[y], tmp);}return false; }int km() {memset(linker, -1, sizeof linker);memset(ly, 0, sizeof ly);for(int i = 0; i < nx; i++) {lx[i] = -INF;for(int j = 0; j < ny; j++)lx[i] = max(lx[i], g[i][j]);}for(int x = 0; x < nx; x++) {for(int i = 0; i < ny; i++)slack[i] = INF;while(true) {memset(visx, 0, sizeof visx);memset(visy, 0, sizeof visy);if(dfs(x)) break;int d = INF;for(int i = 0; i < ny; i++)if(!visy[i] && d > slack[i])d = slack[i];for(int i = 0; i < nx; i++)if(visx[i]) lx[i] -= d;for(int i = 0; i < ny; i++)if(visy[i]) ly[i] += d;else slack[i] -= d;}}int res = 0;for(int i = 0; i < ny; i++) res += g[linker[i]][i];return res; }void read() {memset(g, 0, sizeof g);for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)scanf("%d", &g[i][j]), g[i][j] *= 100;nx = ny = m;int x;init = 0;for(int i = 0; i < n; i++) {scanf("%d", &x), x--;init += g[i][x] / 100;g[i][x]++;} }void work() {int ans = km();printf("%d %d\n", n - ans % 100, ans / 100 - init); }int main() {while(scanf("%d%d", &n, &m)!=EOF) {read();work();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【KM匹配】 HDOJ 2853 Assignment的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。