热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

拆点+KM,建图思路看的题解,求解最小权匹配问题

本文介绍了一种求解最小权匹配问题的方法,使用了拆点和KM算法。通过将机器拆成多个点,表示加工的顺序,然后使用KM算法求解最小权匹配,得到最优解。文章给出了具体的代码实现,并提供了一篇题解作为参考。

题目链接

拆点+KM,建图思路看的题解。。。

看懂的题意后,想了好一会。知道这题是KM,但是不会建图,无奈啊。

建图很巧妙,假如同一个机器上加工了k件物品,那么实际花费时间k*a1+(k-1)*a2+(k-3)*a3....

其实对这个拆点,也不是很懂。

这样把m个机器拆成n个点,表示是第几个加工的。套上模版,这题是求最小权,取一下相反数就行了。

拆成两个集合一个存n个物品,另一个存第i个机器上第j个加工。

1 #include
2 #include
3 #include <string>
4 #include
5 #include
6 using namespace std;
7 #define N 2552
8 #define INF 0x7fffffff
9 int mat[N][N];
10 int inx[N],iny[N];
11 int lx[N],ly[N];
12 int match[N];
13 int n,m;
14 int inp[N][N];
15 int dfs(int u)
16 {
17 inx[u] &#61; 1;
18 int i;
19 for(i &#61; 1; i <&#61; m*n; i &#43;&#43;)
20 {
21 if(!iny[i]&&lx[u]&#43;ly[i] &#61;&#61; mat[u][i])
22 {
23 iny[i] &#61; 1;
24 if(match[i] &#61;&#61; -1||dfs(match[i]))
25 {
26 match[i] &#61; u;
27 return 1;
28 }
29 }
30 }
31 return 0;
32 }
33 void KM()
34 {
35 int i,j,k,temp;
36 for(i &#61; 1;i )
37 {
38 lx[i] &#61; -INF;
39 ly[i] &#61; -INF;
40 }
41 for(i &#61; 1; i <&#61; n; i &#43;&#43;)
42 {
43 for(j &#61; 1; j <&#61; m*n; j &#43;&#43;)
44 lx[i] &#61; max(lx[i],mat[i][j]);
45 }
46 for(i &#61; 1; i <&#61; n; i &#43;&#43;)
47 {
48 for(;;)
49 {
50 memset(inx,0,sizeof(inx));
51 memset(iny,0,sizeof(iny));
52 if(dfs(i))
53 break;
54 else
55 {
56 temp &#61; INF;
57 for(j &#61; 1; j <&#61; n; j &#43;&#43;)
58 {
59 if(inx[j])
60 {
61 for(k &#61; 1; k <&#61; m*n; k &#43;&#43;)
62 {
63 if(!iny[k]&&temp > lx[j]&#43;ly[k]-mat[j][k])
64 temp &#61; lx[j]&#43;ly[k]-mat[j][k];
65 }
66 }
67 }
68 for(j &#61; 1;j <&#61; n;j &#43;&#43;)
69 {
70 if(inx[j])
71 lx[j] -&#61; temp;
72 }
73 for(j &#61; 1;j <&#61; m*n;j &#43;&#43;)
74 {
75 if(iny[j])
76 ly[j] &#43;&#61; temp;
77 }
78 }
79 }
80 }
81 }
82 int main()
83 {
84 int i,j,k,cas;
85 scanf("%d",&cas);
86 while(cas--)
87 {
88 scanf("%d%d",&n,&m);
89 memset(match,-1,sizeof(match));
90 for(i &#61; 1;i <&#61; n;i &#43;&#43;)
91 {
92 for(j &#61; 1;j <&#61; m;j &#43;&#43;)
93 {
94 scanf("%d",&inp[i][j]);
95 }
96 }
97 for(i &#61; 1;i <&#61; n;i &#43;&#43;)
98 {
99 for(j &#61; 1;j <&#61; m;j &#43;&#43;)
100 {
101 for(k &#61; 1;k <&#61; n;k &#43;&#43;)
102 {
103 mat[i][(j-1)*n&#43;k] &#61; -((n-k&#43;1)*inp[i][j]);
104 }
105 }
106 }
107 KM();
108 int ans &#61; 0;
109 for(i &#61; 1;i <&#61; n*m;i &#43;&#43;)
110 {
111 if(match[i] !&#61; -1)
112 ans &#43;&#61; mat[match[i]][i];
113 }
114 printf("%.6lf\n",-ans*1.0/n);
115 }
116 return 0;
117 }

 

转:https://www.cnblogs.com/naix-x/archive/2013/04/17/3027096.html



推荐阅读
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 本文深入探讨 MyBatis 中动态 SQL 的使用方法,包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本章将深入探讨移动 UI 设计的核心原则,帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧,您将能够创建出既美观又实用的移动应用。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]
author-avatar
手机用户随便转转
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有