傳送門(mén)：QAQ

題意:給了你n個(gè)公司和m個(gè)任務(wù)，然后給你了每個(gè)公司處理每個(gè)任務(wù)的效率。然后他已經(jīng)給你了每個(gè)公司的分配方案，讓你求出最多能增大多少效率（即最大權(quán)值匹配減去原來(lái)的），然后問(wèn)你至少要修改多少個(gè)關(guān)系（即修改多少條邊）

思路：因?yàn)楣镜臄?shù)量是比任務(wù)的數(shù)量少的，我們可以確定匹配的邊數(shù)為n條，然后下面很重要，因?yàn)樽畲笃ヅ湮覀兒芎媒鉀Q，但是要盡量修改少的邊就比較麻煩，所以我們要在匹配后區(qū)分老的邊和新的邊，所以有一種方法就是在剛開(kāi)始建圖時(shí)，將老邊的權(quán)值*（n+1）+1，新邊的權(quán)值為*（n+1）【為什么可以這樣建邊去跑km，難道不會(huì)影響每條邊的大小關(guān)系嗎？我們注意，當(dāng)n>=1時(shí)，因?yàn)槭钦麛?shù)擴(kuò)大了（n+1）倍，加一不會(huì)影響兩個(gè)值之間的大小關(guān)系，兩個(gè)相同的值話會(huì)遵循老邊優(yōu)先跑】，這樣我們求出最大匹配后是否就能根據(jù)取模（n+1）來(lái)判斷剩余的邊數(shù)，因?yàn)檫厰?shù)是等于n的，所以只要將最后的權(quán)值除以（n+1）就行了(老邊加的1不會(huì)產(chǎn)生影響)。

附上代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<map> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f const int N = 60; int nx, ny; int g[N][N]; int girl[N], Lx[N], Ly[N]; int slack[N]; bool S[N], T[N]; int n, m; map<pair<int, int>, int>q; bool DFS(int x) {S[x] = true;for (int i = 1; i <= ny; i++) {if (T[i]) continue;int tmp = Lx[x] + Ly[i] - g[x][i];if (tmp == 0){T[i] = true;if (girl[i] == -1 || DFS(girl[i])){girl[i] = x; return true;}}else if (slack[i]>tmp) slack[i] = tmp;}return false; }int KM() {memset(girl, -1, sizeof(girl));memset(Ly, 0, sizeof(Ly));for (int i = 1; i <= nx; i++) {Lx[i] = -INF;for (int j = 1; j <= ny; j++)if (g[i][j]>Lx[i]) Lx[i] = g[i][j];}for (int j = 1; j <= nx; j++) {for (int i = 1; i <= ny; i++) slack[i] = INF;while (true) {memset(S, 0, sizeof(S));memset(T, 0, sizeof(T));if (DFS(j)) break; 。int d = INF;for (int i = 1; i <= ny; i++) if (!T[i] && d>slack[i])d = slack[i];for (int i = 1; i <= nx; i++) if (S[i]) Lx[i] -= d;for (int i = 1; i <= ny; i++) {if (T[i]) Ly[i] += d; else slack[i] -= d;}}}int ans = 0;for (int i = 1; i <= ny; i++) //累計(jì)匹配邊的權(quán)和if (girl[i]>0) ans += g[girl[i]][i];return ans; }int main(void) {int n, m;while (scanf("%d%d", &n, &m) != EOF) {q.clear();memset(g, 0, sizeof(g));for (int i = 1; i <= n; i++) {for (int z = 1; z <= m; z++) {int a;scanf("%d", &a);q[make_pair(i, z)] = a;g[i][z] = a*(n+1);}}int sum = 0;for (int i = 1; i <= n; i++) {int b;scanf("%d", &b);g[i][b] += 1;sum += q[make_pair(i, b)];}nx = n;ny = m;int ans = KM();printf("%d %d\n", n - ans % (n + 1), ans / (n + 1) - sum);} }

?

總結(jié)

以上是生活随笔為你收集整理的Assignment HDU - 2853（二分图匹配 KM）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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