文档章节

Bzoj2395: [Balkan 2011]Timeismoney(最小乘积生成树)

o
 osc_1ee7cxmx
发布于 2018/08/06 20:42
字数 668
阅读 12
收藏 0
sol

问题描述

每条边两个权值 $x,y$,求一棵 $(\sum x) \times (\sum y)$ 最小的生成树

Sol

把每一棵生成树的权值 $\sum x$ 和 $\sum y$ 看成平面上的一个点 $(X,Y)$

那么就是要求 $X \times Y$ 最小

设 $k=X \times Y$,则 $Y = \frac{k}{X}$

也就是要求这个反比例函数最靠近坐标轴

我们知道了 $X$ 最小和 $Y$ 最小的答案(两遍最小生成树)

设这两个点为 $A,B$

那么就是要在 $AB$ 这条直线的左边找到一个距离最远的点 $C$ 来更新当前答案

也就是向量 $\vec {AB}$ 和 $\vec {AC}$ 叉积最小(为负数,也就是面积)

即 $(Bx-Ax)\times (Cy-Ay)-(Cx-Ax) \times (By-Ay)$ 最小

化简就是 $(Bx-Ax)\times Cy-(By-Ay)\times Cx+...$ (省略号为常数)

那么每条边改一下权值为 $(Bx-Ax)\times y-(By-Ay)\times x$

然后求一遍最小生成树求出 $C$,递归处理 $AC$ 和 $CB$ 即可

p.s: 最小乘积匹配也可以这么做

# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
# define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
using namespace std;
typedef long long ll;

IL int Input(){
	RG char c = getchar(); RG int x = 0, z = 1;
	for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x * z;
}

const int maxn(205);
const int maxm(1e4 + 5);
const int inf(1e9);

int n, m, fa[maxn];

struct Point{
	int x, y;

	IL Point operator -(RG Point b) const{
		return (Point){x - b.x, y - b.y};
	}

	IL Point operator +(RG Point b) const{
		return (Point){x + b.x, y + b.y};
	}

	IL int operator *(RG Point b) const{
		return x * b.y - y * b.x;
	}

	IL int operator <(RG Point b) const{
		return x * y != b.x * b.y ? x * y < b.x * b.y : x < b.x;
	}
} ans, mnc, mnt;

struct Edge{
	int u, v, w, c, t;

	IL int operator <(RG Edge b) const{
		return w < b.w;
	}
} edge[maxm];

IL int Find(RG int x){
	return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

IL Point Kruskal(){
	for(RG int i = 1; i <= n; ++i) fa[i] = i;
	RG Point ret = (Point){0, 0};
	sort(edge + 1, edge + m + 1);
	for(RG int i = 1, t = 0; t < n - 1 && i <= m; ++i){
		RG int u = Find(edge[i].u), v = Find(edge[i].v);
		if(u != v) fa[u] = v, ++t, ret = ret + (Point){edge[i].c, edge[i].t};
	}
	ans = min(ans, ret);
	return ret;
}

IL void Solve(RG Point a, RG Point b){
	RG int x = b.y - a.y, y = b.x - a.x;
	for(RG int i = 1; i <= m; ++i) edge[i].w = y * edge[i].t - x * edge[i].c;
	RG Point ret = Kruskal();
	if((b - a) * (ret - a) >= 0) return;
	Solve(a, ret), Solve(ret, b);
}

int main(RG int argc, RG char* argv[]){
	File("2395");
	ans = (Point){inf, 1}, n = Input(), m = Input();
	for(RG int i = 1; i <= m; ++i) edge[i] = (Edge){Input() + 1, Input() + 1, 0, Input(), Input()};
	for(RG int i = 1; i <= m; ++i) edge[i].w = edge[i].c;
	mnc = Kruskal();
	for(RG int i = 1; i <= m; ++i) edge[i].w = edge[i].t;
	mnt = Kruskal();
	Solve(mnc, mnt);
	printf("%d %d\n", ans.x, ans.y);
	return 0;
}

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

如何在Ruby中生成随机字符串 - How to generate a random string in Ruby

问题: I'm currently generating an 8-character pseudo-random uppercase string for "A" .. "Z": 我目前正在为“ A” ..“ Z”生成一个8个字符的伪随机大写字符串: value = ""; 8.times{......

法国红酒甜
45分钟前
12
0
Python中的mkdir -p功能[重复] - mkdir -p functionality in Python [duplicate]

问题: This question already has an answer here: 这个问题在这里已有答案: How can I safely create a nested directory? 如何安全地创建嵌套目录? 25 answers 25个答案 Is there a way...

技术盛宴
今天
15
0
原价500元的认证证书,限时免费考取!

本文作者:y****n 百度云智学院致力于为百度ABC战略(人工智能、大数据、云计算)提供人才生态体系建设,包括基于百度ABC、IoT的课程体系,整合百度优势技术能力的深度学习技术、Apollo无人车...

百度开发者中心
昨天
17
0
在virtualenv中使用Python 3 - Using Python 3 in virtualenv

问题: Using virtualenv , I run my projects with the default version of Python (2.7). 使用virtualenv ,我使用默认版本的Python(2.7)运行项目。 On one project, I need to use Pyth......

富含淀粉
今天
16
0
Python的__init__和self是做什么的? - What __init__ and self do on Python?

问题: I'm learning the Python programming language and I've came across something I don't fully understand. 我正在学习Python编程语言,遇到了一些我不太了解的东西。 In a method ......

javail
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部