hdu 2853 Assignment KM算法

时间:2022-09-18 23:58:03

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2853

Last year a terrible earthquake attacked Sichuan province. About 300,000 PLA soldiers attended the rescue, also ALPCs. Our mission is to solve difficulty problems to optimization the assignment of troops. The assignment is measure by efficiency, which is an integer, and the larger the better.
We have N companies of troops and M missions, M>=N. One
company can get only one mission. One mission can be assigned to only one
company. If company i takes mission j, we can get efficiency Eij.
We have a
assignment plan already, and now we want to change some companies’ missions to
make the total efficiency larger. And also we want to change as less companies
as possible.
 
题目描述:n个组和m个任务,Eij表示第i个组完成第j个任务的效率,每个组只能完成一个任务,每个任务只能由一个组完成,目前已经有了一个计划,但是现在我们想要让总效率达到最大,并且在此前提下还需要改变重新分配任务的组的个数最少。求出最大效率减去原先计划的效率和重新分配任务的组的个数。
 
算法分析:这道题的思维方式的确很独特,也很巧妙。首先解决第一个问题:最大效率减去原先计划的效率的差值。最大效率很好解决,用KM算法即可,原先计划的效率直接根据输入统计即可。那么第二个问题呢?重新分配任务的组的最小个数。
方法一:首先为了保证在最大效率情况下尽量选择原先已经分配了的任务,所以我们可以对原先已经分配了的任务在效率上加1,这样即使两个组对同一个任务效率相同也会选择原先的计划,然后我们标记一下有哪些边是原先计划里的。剩下的就是KM了。
说明:这种方法为什么会WA呢,还没有找到原因, 关键在于对每条边权都要乘以一个k(k>n),下面的代码就没有乘以k,想想应该是这种方法下求得的不是最大效率吧,但为什么不是最大效率呢? 每条边都乘以k最后的最大效率再除以k,和直接求得的最大效率不是一样的吗?
若有大牛明白其中奥妙,还望指点一二,在此感谢。
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int maxn=; int n,m,k,sum;
int lx[maxn],ly[maxn],visx[maxn],visy[maxn];
int link[maxn],slack[maxn],w[maxn][maxn];
int vis[maxn][maxn]; int dfs(int x)
{
visx[x]=;
for (int y= ;y<=m ;y++)
{
if (visy[y]) continue;
int t=lx[x]+ly[y]-w[x][y];
if (t==)
{
visy[y]=;
if (link[y]==- || dfs(link[y]))
{
link[y]=x;
return ;
}
}
else if (slack[y]>t) slack[y]=t;
}
return ;
} void KM()
{
memset(link,-,sizeof(link));
memset(ly,,sizeof(ly));
for (int i= ;i<=n ;i++)
{
lx[i]=-inf;
for (int j= ;j<=m ;j++)
lx[i]=max(lx[i],w[i][j]);
}
for (int x= ;x<=n ;x++)
{
for (int i= ;i<=m ;i++) slack[i]=inf;
while ()
{
memset(visx,,sizeof(visx));
memset(visy,,sizeof(visy));
if (dfs(x)) break;
int d=inf;
for (int i= ;i<=m ;i++)
{
if (!visy[i] && slack[i]<d) d=slack[i];
}
for (int i= ;i<=n ;i++)
if (visx[i]) lx[i] -= d;
for (int i= ;i<=m ;i++)
{
if (visy[i]) ly[i] += d;
else slack[i] -= d;
}
}
}
int ans=,cnt=;
for (int i= ;i<=m ;i++)
{
if (link[i]!=-)
{
ans += w[link[i] ][i];
if (vis[link[i] ][i]) cnt++;
}
}
printf("%d %d\n",n-cnt,ans-sum-cnt);
// for (int i=1 ;i<=m ;i++)
// {
// if (link[i]!=-1) ans += w[link[i] ][i];
// }
// printf("%d %d\n",n-ans%k,ans/k-sum);
} int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(w,,sizeof(w));
memset(vis,,sizeof(vis));
k=;
for (int i= ;i<=n ;i++)
{
for (int j= ;j<=m ;j++)
{
scanf("%d",&w[i][j]);
/// w[i][j] *= k;
}
}
int a;
sum=;
for (int i= ;i<=n ;i++)
{
scanf("%d",&a);
sum += w[i][a];
///sum += w[i][a]/k;
w[i][a] ++ ;
vis[i][a]=;
}
KM();
}
return ;
}

方法二:和方法一的区别就在于对每条边都乘以k(比如k=200),对于原有匹配w[x][y]++,最后的答案最大效率为ans。

那么差值=ans/k-sum;个数=n-ans%k。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int maxn=; int n,m,k,sum;
int lx[maxn],ly[maxn],visx[maxn],visy[maxn];
int link[maxn],slack[maxn],w[maxn][maxn]; int dfs(int x)
{
visx[x]=;
for (int y= ;y<=m ;y++)
{
if (visy[y]) continue;
int t=lx[x]+ly[y]-w[x][y];
if (t==)
{
visy[y]=;
if (link[y]==- || dfs(link[y]))
{
link[y]=x;
return ;
}
}
else if (slack[y]>t) slack[y]=t;
}
return ;
} void KM()
{
memset(link,-,sizeof(link));
memset(ly,,sizeof(ly));
for (int i= ;i<=n ;i++)
{
lx[i]=-inf;
for (int j= ;j<=m ;j++)
lx[i]=max(lx[i],w[i][j]);
}
for (int x= ;x<=n ;x++)
{
for (int i= ;i<=m ;i++) slack[i]=inf;
while ()
{
memset(visx,,sizeof(visx));
memset(visy,,sizeof(visy));
if (dfs(x)) break;
int d=inf;
for (int i= ;i<=m ;i++)
{
if (!visy[i] && slack[i]<d) d=slack[i];
}
for (int i= ;i<=n ;i++)
if (visx[i]) lx[i] -= d;
for (int i= ;i<=m ;i++)
{
if (visy[i]) ly[i] += d;
else slack[i] -= d;
}
}
}
int ans=,cnt=;
for (int i= ;i<=m ;i++)
{
if (link[i]!=-) ans += w[link[i] ][i];
}
printf("%d %d\n",n-ans%k,ans/k-sum);
} int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(w,,sizeof(w));
k=;
for (int i= ;i<=n ;i++)
{
for (int j= ;j<=m ;j++)
{
scanf("%d",&w[i][j]);
w[i][j] *= k;
}
}
int a;
sum=;
for (int i= ;i<=n ;i++)
{
scanf("%d",&a);
sum += w[i][a]/k;
w[i][a] ++ ;
}
KM();
}
return ;
}

hdu 2853 Assignment KM算法的更多相关文章

  1. 【HDU 2853】 KM算法

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2853 题意:有n个公司,m个任务,每个公司做每个任务都有一个效率值,最开始每个公司都指派了一个任务,现 ...

  2. HDU 2853 Assignment(KM最大匹配好题)

    HDU 2853 Assignment 题目链接 题意:如今有N个部队和M个任务(M>=N),每一个部队完毕每一个任务有一点的效率,效率越高越好.可是部队已经安排了一定的计划,这时须要我们尽量用 ...

  3. HDU&lpar;2255&rpar;,KM算法,最大权匹配

    题目链接 奔小康赚大钱 Time Limit: 1000/1000MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Su ...

  4. HDU 2853 最大匹配&amp&semi;KM模板

    http://acm.hdu.edu.cn/showproblem.php?pid=2853 这道题初看了没有思路,一直想的用网络流如何解决 参考了潘大神牌题解才懂的 最大匹配问题KM 还需要一些技巧 ...

  5. HDU 2853 &amp&semi; 剩余系&plus;KM模板

    题意: 给你一张二分图,给一个原匹配,求原匹配改动最少的边数使其边权和最大. SOL: 我觉得我的智商还是去搞搞文化课吧..这种题给我独立做我大概只能在暴力优化上下功夫.. 这题的处理方法让我想到了剩 ...

  6. 【HDU 2853】Assignment (KM)

    Assignment Problem Description Last year a terrible earthquake attacked Sichuan province. About 300, ...

  7. Assignment &lpar;HDU 2853 最大权匹配KM&rpar;

    Assignment Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total ...

  8. Assignment HDU - 2853(二分图匹配 KM 新边旧边)

    传送门: Assignment HDU - 2853 题意:题意直接那松神的题意了.给了你n个公司和m个任务,然后给你了每个公司处理每个任务的效率.然后他已经给你了每个公司的分配方案,让你求出最多能增 ...

  9. hdu 2426 Interesting Housing Problem 最大权匹配KM算法

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2426 For any school, it is hard to find a feasible ac ...

随机推荐

  1. 让你少走弯路的搭建树莓派的Net与NodeJS运行环境

      树莓派是当前最火的嵌入计算平台没有之一,树莓派可以给我们无数的想象,树莓派的高性能.低功耗.低成本.可扩展性(最新的树莓派原生支持WIFI和蓝牙,这功能太赞了)深受大家的喜爱.虽然树莓派到目前为止 ...

  2. 前端 js 实现简单 表单提交

    1. 登录页 验证用户身份,登录成功之后等待一定秒数,跳转到操作页面 <html> <head> <title>Login.html</title> & ...

  3. MySQL5&period;7&lpar;5&period;6&rpar;GTID环境下恢复从库思&lpar;qi&rpar;路&lpar;yin&rpar;方&lpar;ji&rpar;法&lpar;qiao&rpar;

      要讨论如何恢复从库,我们得先来了解如下一些概念: GTID_EXECUTED:它是一组包含已经记录在二进制日志文件中的事务集合 GTID_PURGED:它是一组包含已经从二进制日志删除掉的事务集合 ...

  4. 上海邮政EMS海关清关(个人) 流程

    最近雾埋越来越严重,上个星期买了一个tacx骑行台,不料运气欠佳,被税了.那就去乖乖缴税吧. 拿着EMS的通知单(没有通知单就不要去了),到通知单指定的地址(上海有两处,我的是武定路458号)清关提货 ...

  5. git删除远程分支和本地分支

    问题描述:       当我们集体进行项目时,将自定义分支push到主分支master之后,如何删除远程的自定义分支呢 问题解决:        (1)使用命令git branch -a 查看所有分支 ...

  6. 一个不错的JavaScript解析浏览器路径方法(转)

    JavaScript中有时需要用到当前的请求路径等涉及到url的情况,正常情况下我们可以使用location对象来获取我们需要的信息,本文从另外一个途径来解决这个问题,而且更加巧妙 方法如下: fun ...

  7. 关于JavaScript的模块化

    为什么需要模块化 最近在学习网易微专业的<前端系统架构>课程,里面讲到了关于JavaScript的模块化问题.具体指的是当随着Web系统不断强大起来,需要在客户端进行的操作就多了起来(比如 ...

  8. linux下导入、导出mysql数据库命令的实现方法

    首先建空数据库 mysql>create database abc; 导入数据库 mysql>use abc; 设置数据库编码 mysql>set names utf8; 导入数据( ...

  9. PAT A1010&period;Radix 二分法

    PAT A1010.Radix 链接: https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536 算法 ...

  10. ZooKeeper集群详细安装教程

    1. 安装JDK 1.1 官网下载JDK 进入网址<a href="http://www.oracle.com/technetwork/java/javase/downloads/jd ...