问题描述

每条边两个权值 \(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;

}

巴特西

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

问题描述

Sol

最新文章

热门文章