BZOJ 2395 [Balkan 2011]Time is money

题面

题解

将\(\sum_i c_i\)和\(\sum_i t_i\)分别看做分别看做\(x\)和\(y\)，投射到平面直角坐标系中，于是就是找\(xy\)最小的点

于是可以先找出\(x\)最小的点\(\mathrm{A}\)和\(y\)最小的点\(\mathrm{B}\)，然后找到在\(\mathrm{AB}\)左下方的最远的点\(\mathrm{C}\)，如图所示：

即\(\overrightarrow{\mathrm{AB}} \times \overrightarrow{\mathrm{AC}}\)最小（因为\(\overrightarrow{\mathrm{AB}} \times \overrightarrow{\mathrm{AC}} \leq 0\)）

\[\begin{aligned}
\because \overrightarrow{\mathrm{AB}} \times \overrightarrow{\mathrm{AC}} &= (x_{\mathrm{B}} - x_{\mathrm{A}})(y_{\mathrm{C}} - y_{\mathrm{A}}) - (y_{\mathrm{B}} - y_{\mathrm{A}})(x_\mathrm{C} - x_\mathrm{A}) \\
&= (x_\mathrm B - x_\mathrm A) \times y_\mathrm C + (y_\mathrm A - y_\mathrm B) \times x_\mathrm C + y_\mathrm B x_\mathrm A - x_\mathrm B y_\mathrm A
\end{aligned}
\]

然后发现只要\((x_\mathrm B - x_\mathrm A) \times y_\mathrm C + (y_\mathrm A - y_\mathrm B) \times x_\mathrm C\)最小即可。

将每条边的权值改为\(\mathrm{g}[i][j] = (y_\mathrm A - y_\mathrm B) \times c[i][j] + (x_\mathrm B - x_\mathrm A)\times t[i][j]\)，跑一遍最小生成树就可以得出答案了。

找到\(\mathrm C\)之后用叉积判断一下\(\mathrm C\)是不是在\(\mathrm{AB}\)的下方，如果是的话，就递归处理\(\mathrm{AC, CB}\)

复杂度？O(能过)

因为\(\mathrm{A, B, C}\)肯定在凸包上，又\(n\)个点的凸包期望点数为\(\sqrt{\ln n}\)，

于是复杂度为\(\mathrm{O}(\sqrt{\ln n!} \times n^2)\)或者\(\mathrm{O}(\sqrt{\ln n!} \times m\log m)\)

代码

#include<cstdio>

#include<cctype>

#include<algorithm>

#define RG register

const int N(210), INF(1e9);

struct vector { int x, y; };

vector ans = (vector) {INF, INF};

inline vector operator - (const vector &lhs, const vector &rhs)

	{ return (vector) {lhs.x - rhs.x, lhs.y - rhs.y}; }

inline int operator * (const vector &lhs, const vector &rhs)

	{ return lhs.x * rhs.y - lhs.y * rhs.x; }

int g[N][N], f[N][N], dis[N], c[N][N], t[N][N], cdis[N], tdis[N], vis[N], n, m;

vector prim(int valx, int valy)

{

	for(RG int i = 1; i <= n; i++)

		for(RG int j = 1; j <= n; j++)

			if(f[i][j]) g[i][j] = valx * c[i][j] + valy * t[i][j];

	std::fill(dis + 1, dis + n + 1, INF);

	std::fill(vis + 1, vis + n + 1, 0);

	dis[1] = cdis[1] = tdis[1] = 0;

	vector res = (vector) {0, 0};

	for(RG int i = 1; i <= n; i++)

	{

		int _min = INF, x = -1;

		for(RG int j = 1; j <= n; j++)

			if(_min > dis[j] && (!vis[j])) _min = dis[j], x = j;

		if(_min == INF) break; vis[x] = 1;

		res.x += cdis[x], res.y += tdis[x];

		for(RG int j = 1; j <= n; j++) if(f[x][j])

			if(dis[j] > g[x][j]) dis[j] = g[x][j],

				cdis[j] = c[x][j], tdis[j] = t[x][j];

	}

	long long sum = 1ll * res.x * res.y, _min = 1ll * ans.x * ans.y;

	if(sum < _min || (sum == _min && res.x < ans.x)) ans = res;

	return res;

}

void solve(const vector &A, const vector &B)

{

	vector C = prim(A.y - B.y, B.x - A.x);

	if((B - A) * (C - A) >= 0) return;

	solve(A, C); solve(C, B);

}

int main()

{

	scanf("%d%d", &n, &m);

	for(RG int i = 1, x, y, _c, _t; i <= m; i++)

		scanf("%d%d%d%d", &x, &y, &_c, &_t), ++x, ++y,

		c[x][y] = c[y][x] = _c, t[x][y] = t[y][x] = _t,

		f[x][y] = f[y][x] = 1;

	vector A = prim(1, 0), B = prim(0, 1);

	solve(A, B); printf("%d %d\n", ans.x, ans.y);

	return 0;

}