Assignment HDU - 2853（二分图匹配 KM）

传送门：QAQ

题意:给了你n个公司和m个任务，然后给你了每个公司处理每个任务的效率。然后他已经给你了每个公司的分配方案，让你求出最多能增大多少效率（即最大权值匹配减去原来的），然后问你至少要修改多少个关系（即修改多少条边）

思路：因为公司的数量是比任务的数量少的，我们可以确定匹配的边数为n条，然后下面很重要，因为最大匹配我们很好解决，但是要尽量修改少的边就比较麻烦，所以我们要在匹配后区分老的边和新的边，所以有一种方法就是在刚开始建图时，将老边的权值*（n+1）+1，新边的权值为*（n+1）【为什么可以这样建边去跑km，难道不会影响每条边的大小关系吗？我们注意，当n>=1时，因为是整数扩大了（n+1）倍，加一不会影响两个值之间的大小关系，两个相同的值话会遵循老边优先跑】，这样我们求出最大匹配后是否就能根据取模（n+1）来判断剩余的边数，因为边数是等于n的，所以只要将最后的权值除以（n+1）就行了(老边加的1不会产生影响)。

附上代码：

#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++) //累计匹配边的权和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);} }

 

总结

以上是生活随笔为你收集整理的Assignment HDU - 2853（二分图匹配 KM）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。