2395: [Balkan 2011]Timeismoney

2395: [Balkan 2011]Timeismoney

2395: [Balkan 2011]Timeismoney

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 659 Solved: 359
[Submit][Status][Discuss]
Description

有n个城市(编号从0..n-1)，m条公路(双向的)，从中选择n-1条边，使得任意的两个城市能够连通，一条边需要的c的费用和t的时间，定义一个方案的权值v=n-1条边的费用和*n-1条边的时间和，你的任务是求一个方案使得v最小
Input

第一行两个整数n,m,接下来每行四个整数a,b,c,t,表示有一条公路从城市a到城市b需要t时间和费用c
Output

【output】timeismoney.out
仅一行两个整数sumc，sumt,（sumc表示使得v最小时的费用和，sumc表示最小的时间和） 如果存在多个解使得sumc*sumt相等，输出sumc最小的
Sample Input

5 7

0 1 161 79

0 2 161 15

0 3 13 153

1 4 142 183

2 4 236 80

3 4 40 241

2 1 65 92

Sample Output

279 501

HINT

【数据规模】

1<=N<=200

1<=m<=10000

0<=a,b<=n-1

0<=t,c<=255

有5%的数据m=n-1

有40%的数据有t=c

对于100%的数据如上所述

Source

[Submit][Status][Discuss]

这就是一个裸的最小乘积生成树
对于这类问题，貌似有个统称叫做乘积规划
反正都是能用一类方法解决的
将每种合法的生成树方案看做二维平面上的一个点 (x,y) $(x,y)$
其中 x $x$等于所选边的费用和，y$y$等于所选边的时间和
那么目标等价于使得 k=xy $k=xy$取得最小值
即让函数 y=kx $y=frac kx$尽可能地贴近坐标轴
将所有点画在平面上，那么最优解一定存在与左下角的凸包上
考虑如何求出这块区域上的点
一开始先确定两种方案，记 A $A$为令x$x$最小的方案， B $B$为令y$y$最小的方案
那么一定是在直线 AB $AB$左下方的点才可能出现在凸包
找到一个点 C $C$，使得它尽可能贴近坐标轴
那么这个点C$C$一定是尽量离 AB $AB$远一些
于是就等价于 SΔABC $SDelta ABC$尽量大
即 AB→×AC→ $vec {AB} times vec{AC}$取最小值
暴力展开一下上面的式子就会发现。。。
真的变成做一棵最小生成树了
特别地，如果最小生成树权值为非负数，说明找不到这样的点了
递归解决 (A,C) $(A,C)$和 (C,B) $(C,B)$就行了
注：随机情况下 n $n$个点凸包上的点数期望是lnn−−−√$sqrt {ln n}$
那么复杂度就十分科学了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;const int maxn = 202;
const int maxm = 1E4 + 10;
typedef long long LL;struct E{int a,b,x,y; E(){}E(int a,int b,int x,int y): a(a),b(b),x(x),y(y){}bool operator < (const E &B) const {return x < B.x;}
}e[maxm],_e[maxm];struct Point{int x,y; Point(){}Point(int x,int y): x(x),y(y){}bool operator < (const Point &B){if (1LL * x * y < 1LL * B.x * B.y) return 1;if (1LL * x * y > 1LL * B.x * B.y) return 0;return x < B.y;}
}Ans;int n,m,cnt,fa[maxn],vis[maxm];inline int getfa(int k) {return k == fa[k] ? k : fa[k] = getfa(fa[k]);}inline void Kruskal(Point &C,int dx,int dy,int delta)
{for (int i = 0; i < n; i++) fa[i] = i; ++cnt;for (int i = 1; i <= m; i++)_e[i] = E(e[i].a,e[i].b,dx * e[i].x + dy * e[i].y,i);LL sum = 0; sort(_e + 1,_e + m + 1);for (int i = 1; i <= m; i++){E k = _e[i];int fx = getfa(k.a),fy = getfa(k.b);if (fx == fy) continue;fa[fx] = fy; sum += 1LL * k.x; vis[k.y] = cnt; }sum += 1LL * delta; C = Point(0,0);if (sum >= 0) {C = Point(-1,-1); return;}for (int i = 1; i <= m; i++)if (vis[i] == cnt) C.x += e[i].x,C.y += e[i].y;
}void Pre_Work(Point &C,int dx,int dy)
{C = Point(0,0); ++cnt;for (int i = 0; i < n; i++) fa[i] = i;for (int i = 1; i <= m; i++)_e[i] = E(e[i].a,e[i].b,dx * e[i].x + dy * e[i].y,i);sort(_e + 1,_e + m + 1);for (int i = 1; i <= m; i++){E k = _e[i];int fx = getfa(k.a),fy = getfa(k.b);if (fx == fy) continue;fa[fx] = fy; vis[k.y] = cnt;}for (int i = 1; i <= m; i++)if (vis[i] == cnt) C.x += e[i].x,C.y += e[i].y;
}inline void Dfs(Point A,Point B)
{Point C; int now;now = A.x * B.y - B.x * A.y;Kruskal(C,A.y - B.y,B.x - A.x,now);if (C.x == -1 && C.y == -1) return;if (C < Ans) Ans = C; Dfs(A,C); Dfs(C,B);
}inline int getint()
{char ch = getchar(); int ret = 0;while (ch < '0' || '9' < ch) ch = getchar();while ('0' <= ch && ch <= '9')ret = ret * 10 + ch - '0',ch = getchar();return ret;
}int main()
{#ifdef DMCfreopen(&#","r",stdin);#endifn = getint(); m = getint();for (int i = 1; i <= m; i++){int a,b,x,y;a = getint(); b = getint();x = getint(); y = getint();e[i] = E(a,b,x,y);}Point A,B; Pre_Work(A,1,0); Pre_Work(B,0,1);Ans = A; if (B < Ans) Ans = B;Dfs(A,B); printf("%d %dn",Ans.x,Ans.y);return 0;
}