正文
【算法】最小乘积生成树 & 最小乘积匹配 （HNOI2014画框）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
今天考试的时候果然题目太难于是我就放弃了……转而学习了一下最小乘积生成树。
最小乘积生成树定义：
（摘自网上一篇博文）。
我们主要解决的问题就是当k = 2时，如何获得最小的权值乘积。我们注意到一张图可以有很多棵生成树，我们将每一棵生成树的权值记为（x, y），表示第一种权值之和为x, 第二种权值之和为y. 这样，很自然联想到二维平面上的坐标，每一棵生成树即为这个平面上的一个点。我们所想要寻找的点就是x * y最小的点。这样的点在什么位置？显然，若x1 <= x2, y1 <= y2,1号点的权值必然更小。所以我们的答案只可能处于这张平面图上的凸包的下凸壳上。
于是我们找到A，B两点，一个离y轴最近，一个离x轴最近，这两个点一定是下凸壳的两个端点。之后，我们再寻找到与AB距离最远的点C，用点C 更新答案后再以AC，BC为新的边向下递归求解。此时问题来了：如何找到这一个距离最远，且在AB下方的C点呢？我们将距离转化为面积，使用叉积求解。因为要求C点在AB下方，所以得到的叉积必为负数。又因为|叉积| = 四边形面积，所以得到的叉积必然是负的值中绝对值最大的那一个，即求解出与AB构成的叉积最小的C点。
然后就开始考虑式子的转化：min (B - A) * (C - A) = (B.x - A.x) (C.x - A.x) - (C.x - A.x) (B.y - A.y); 化开这个式子，省去常数部分，我们发现所求就是（A.y - B.y）* a[i][j] - （A.x - B.x）* b[i][j] 最小。我们考虑将这个东西看做权值，就可以用Kruskal求出使这个值最小的C点了。如果是匹配的话，则将i --> j 视作匹配的权值，将权值取反（因为要求求最小）后跑KM算法获得最大权值匹配。
下面的代码是仿照着的，但觉得写的很漂亮，放在这里大家可以参考一下。感谢原本的博主~
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000
#define INF 99999999
int n, ans = INF, lx[maxn], ly[maxn], s[maxn], match[maxn];
int T, g[maxn][maxn], a[maxn][maxn], b[maxn][maxn];
bool visx[maxn], visy[maxn];struct vec
{
int x, y;
};vec operator -(vec a, vec b)
{
return (vec) { b.x - a.x, b.y - a.y };
}int operator *(vec a, vec b)
{
return a.x * b.y - a.y * b.x;
}int read()
{
int x = , k = ;
char c;
c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
}struct Graph
{
void build(int wx, int wy)
{
for(int i = ; i <= n; i ++)
for(int j = ; j <= n; j ++)
g[i][j] = - (wx * a[i][j] + wy * b[i][j]);
} bool dfs(int u)
{
visx[u] = ;
for(int v = ; v <= n; v ++)
{
if(visy[v]) continue;
int tem = lx[u] + ly[v] - g[u][v];
if(!tem)
{
visy[v] = ;
if(!match[v] || dfs(match[v]))
{
match[v] = u;
return ;
}
}
else s[v] = min(s[v], tem);
}
return false;
} vec KM()
{
memset(lx, , sizeof(lx)), memset(ly, , sizeof(ly));
memset(match, , sizeof(match));
for(int i = ; i <= n; i ++)
for(int j = ; j <= n; j ++)
lx[i] = max(lx[i], g[i][j]);
for(int i = ; i <= n; i ++)
{
memset(s, , sizeof(s));
while()
{
memset(visx, , sizeof(visx)), memset(visy, , sizeof(visy));
if(dfs(i)) break;
int tem = INF;
for(int j = ; j <= n; j ++)
if(!visy[j]) tem = min(tem, s[j]);
for(int j = ; j <= n; j ++)
if(visx[j]) lx[j] -= tem;
for(int j = ; j <= n; j ++)
if(visy[j]) ly[j] += tem;
else s[j] -= tem;
}
}
vec re; re.x = , re.y = ;
for(int i = ; i <= n; i ++)
re.x += a[match[i]][i], re.y += b[match[i]][i];
return re;
}
}G;void Solve(vec A, vec B)
{
G.build(A.y - B.y, B.x - A.x);
vec C = G.KM();
ans = min(ans, C.x * C.y);
if((A - B) * (A - C) >= ) return;
Solve(A, C), Solve(C, B);
}int main()
{
T = read();
while(T --)
{
n = read();
for(int i = ; i <= n; i ++)
for(int j = ; j <= n; j ++)
a[i][j] = read();
for(int i = ; i <= n; i ++)
for(int j = ; j <= n; j ++)
b[i][j] = read();
G.build(, );
vec A = G.KM();
G.build(, );
vec B = G.KM();
ans = min(A.x * A.y, B.x * B.y);
Solve(A, B);
printf("%d\n", ans);
}
return ;
}
【算法】最小乘积生成树 & 最小乘积匹配 （HNOI2014画框）的更多相关文章- 树（最小乘积生成树,克鲁斯卡尔算法）：BOI timeismoney
The NetLine company wants to offer broadband internet to N towns. For this, it suffices to construct ...
- Bzoj2395: [Balkan 2011]Timeismoney(最小乘积生成树)
问题描述 每条边两个权值 \(x,y\),求一棵 \((\sum x) \times (\sum y)\) 最小的生成树 Sol 把每一棵生成树的权值 \(\sum x\) 和 \(\sum y\) ...
- bzoj2395[Balkan 2011]Timeismoney最小乘积生成树
所谓最小乘积生成树,即对于一个无向连通图的每一条边均有两个权值xi,yi,在图中找一颗生成树,使得Σxi*Σyi取最小值. 直接处理问题较为棘手,但每条边的权值可以描述为一个二元组(xi,yi),这也 ...
- HDU5697 刷题计划 dp+最小乘积生成树
分析:就是不断递归寻找靠近边界的最优解 学习博客(必须先看这个): 1:http://www.cnblogs.com/autsky-jadek/p/3959446.html 2:http://blog ...
- 【BZOJ2395】【Balkan 2011】Timeismoney 最小乘积生成树
链接: #include <stdio.h> int main() { puts("转载请注明出处[辗转山河弋流歌 by 空灰冰魂]谢谢"); puts("网 ...
- Luogu5540 最小乘积生成树
Luogu5540 最小乘积生成树 题目链接:洛谷 题目描述:对于一个\(n\)个点\(m\)条边的无向连通图,每条边有两个边权\(a_i,b_i\),求使\((\sum a_i)\times (\s ...
- P5540-[BalkanOI2011]timeismoney|最小乘积生成树【最小生成树,凸壳】
正题 题目链接:https://www.luogu.com.cn/problem/P5540 题目大意 给出\(n\)个点\(m\)条边边权是一个二元组\((a_i,b_i)\),求出一棵生成树最小化 ...
- bzoj2395 [Balkan 2011]Timeismoney（最小乘积生成树+计算几何）
题意 每条边有两个权值\(c,t\),请求出一颗生成树,使得\(\sum c\times \sum t\)最小 题解 为什么生成树会和计算几何扯上关系-- 对于每棵树,设\(x=c,y=t\),我们可 ...
- BZOJ2395 [Balkan 2011]Timeismoney 【最小乘积生成树】
题目链接 BZOJ2395 题意:无向图中每条边有两种权值,定义一个生成树的权值为两种权值各自的和的积 求权值最小的生成树 题解 如果我们将一个生成树的权值看做坐标,那么每一个生成树就对应一个二维平面 ...
随机推荐- NetAnalyzer笔记 之 八 NetAnalyzer2016使用方法（2）
[创建时间:2016-05-06 22:07:00] NetAnalyzer下载地址 在写本篇的时候,NetAnalyzer 3.1版本已经发布,所以本篇就以最新版本的为例继续使用,并且顺带说明一下, ...
- 发布(Windows)
发布(Windows) 本篇将在这个系列演示的例子上继续记录Asp.Net Core在Windows上发布的过程. Asp.Net Core在Windows上可以采用两种运行方式.一种是自托管运行,另 ...
- windows server 2008 应用程序池自动关闭 C:\Windows\system32\RpcProxy\RpcProxy.dll failed to load
Sign In Join Search IIS Home Downloads Learn Reference Solutions Blogs Forums HomeIIS.NET Forums64-b ...
- Cross platform GUI for creating SSL certs with OpenSSL
Someone said: from : https://micksmix.wordpress.com/2012/08/09/xca-cross-platform-gui-for-creating-s ...
- C++中的new/delete
不同于C语言中的malloc/free是库函数,C++语言中的new/delete是运算符,而不是库函数. new/delete执行流程 我们经常会接触到的是new/delete operator(就 ...
- Google揭开Mesa的神秘面纱——一个具备跨地域复制和近实时特性的可伸缩数据仓库
http://www.infoq.com/cn/news/2014/08/google-data-warehouse-mesa Google发表了一篇新的论文,该论文描述了他们内部所使用的一个被称为M ...
- 《MySQL技术内幕》读书笔记
序章 MySQL的安装 源码编译安装 MySQL的配置 基础配置 mysqld程序:语言设置 mysqld程序:通信.网络.信息安全 mysqld程序:内存管理.优化.查询缓存区 mysqld程序:日 ...
- 关于对最新HTML总结PPT讲稿的分享
如果大家还记得HTML,那么2009年的时候可能当时还是HTML1.0时代,而国际化的标准才刚刚开始,对于TABLE表格的使用,还有就是一些常用的标签都是及为简单的,因为当时的代码都是接近于短码,所以 ...
- MYSQL学习笔记 （一）
每次面试后,都决定一改前非.事实上依然和那些发誓再吃最后一份美食的胖子一样.不管这次是不是三分钟热度但是至少我开始. MYSQL引擎 说到MYSQL引擎我又想起研二时候去面试的第一家公司 ...
- js代码定义类代码的领悟
var Class = { create: function() { return function() { this.initialize.apply(this, argumen ...
The NetLine company wants to offer broadband internet to N towns. For this, it suffices to construct ...
问题描述 每条边两个权值 \(x,y\),求一棵 \((\sum x) \times (\sum y)\) 最小的生成树 Sol 把每一棵生成树的权值 \(\sum x\) 和 \(\sum y\) ...
所谓最小乘积生成树,即对于一个无向连通图的每一条边均有两个权值xi,yi,在图中找一颗生成树,使得Σxi*Σyi取最小值. 直接处理问题较为棘手,但每条边的权值可以描述为一个二元组(xi,yi),这也 ...
分析:就是不断递归寻找靠近边界的最优解 学习博客(必须先看这个): 1:http://www.cnblogs.com/autsky-jadek/p/3959446.html 2:http://blog ...
链接: #include <stdio.h> int main() { puts("转载请注明出处[辗转山河弋流歌 by 空灰冰魂]谢谢"); puts("网 ...
Luogu5540 最小乘积生成树 题目链接:洛谷 题目描述:对于一个\(n\)个点\(m\)条边的无向连通图,每条边有两个边权\(a_i,b_i\),求使\((\sum a_i)\times (\s ...
正题 题目链接:https://www.luogu.com.cn/problem/P5540 题目大意 给出\(n\)个点\(m\)条边边权是一个二元组\((a_i,b_i)\),求出一棵生成树最小化 ...
题意 每条边有两个权值\(c,t\),请求出一颗生成树,使得\(\sum c\times \sum t\)最小 题解 为什么生成树会和计算几何扯上关系-- 对于每棵树,设\(x=c,y=t\),我们可 ...
题目链接 BZOJ2395 题意:无向图中每条边有两种权值,定义一个生成树的权值为两种权值各自的和的积 求权值最小的生成树 题解 如果我们将一个生成树的权值看做坐标,那么每一个生成树就对应一个二维平面 ...
- NetAnalyzer笔记 之 八 NetAnalyzer2016使用方法（2）
[创建时间:2016-05-06 22:07:00] NetAnalyzer下载地址 在写本篇的时候,NetAnalyzer 3.1版本已经发布,所以本篇就以最新版本的为例继续使用,并且顺带说明一下, ...
- 发布(Windows)
发布(Windows) 本篇将在这个系列演示的例子上继续记录Asp.Net Core在Windows上发布的过程. Asp.Net Core在Windows上可以采用两种运行方式.一种是自托管运行,另 ...
- windows server 2008 应用程序池自动关闭 C:\Windows\system32\RpcProxy\RpcProxy.dll failed to load
Sign In Join Search IIS Home Downloads Learn Reference Solutions Blogs Forums HomeIIS.NET Forums64-b ...
- Cross platform GUI for creating SSL certs with OpenSSL
Someone said: from : https://micksmix.wordpress.com/2012/08/09/xca-cross-platform-gui-for-creating-s ...
- C++中的new/delete
不同于C语言中的malloc/free是库函数,C++语言中的new/delete是运算符,而不是库函数. new/delete执行流程 我们经常会接触到的是new/delete operator(就 ...
- Google揭开Mesa的神秘面纱——一个具备跨地域复制和近实时特性的可伸缩数据仓库
http://www.infoq.com/cn/news/2014/08/google-data-warehouse-mesa Google发表了一篇新的论文,该论文描述了他们内部所使用的一个被称为M ...
- 《MySQL技术内幕》读书笔记
序章 MySQL的安装 源码编译安装 MySQL的配置 基础配置 mysqld程序:语言设置 mysqld程序:通信.网络.信息安全 mysqld程序:内存管理.优化.查询缓存区 mysqld程序:日 ...
- 关于对最新HTML总结PPT讲稿的分享
如果大家还记得HTML,那么2009年的时候可能当时还是HTML1.0时代,而国际化的标准才刚刚开始,对于TABLE表格的使用,还有就是一些常用的标签都是及为简单的,因为当时的代码都是接近于短码,所以 ...
- MYSQL学习笔记 （一）
每次面试后,都决定一改前非.事实上依然和那些发誓再吃最后一份美食的胖子一样.不管这次是不是三分钟热度但是至少我开始. MYSQL引擎 说到MYSQL引擎我又想起研二时候去面试的第一家公司 ...
- js代码定义类代码的领悟
var Class = { create: function() { return function() { this.initialize.apply(this, argumen ...
