[BalkanOI2011] timeismoney | 最小乘积生成树
题目描述
给出一个 $n$ 个点 $m$ 条边的无向图,第 $i$ 条边有两个权值 $a_i$ 和 $b_i$ 。
求该图的一棵生成树 $T$ ,使得
$$\left(\sum_{e\in T}a_e\right)\times\left(\sum_{e\in T}b_e\right)$$
最小。
输入输出格式
输入格式
第一行两个正整数 $n,m$ 。
下 $m$ 行,每行 $4$ 个整数 $u_i,v_i,a_i,b_i$ ,表示第 $i$ 条边连接 $u_i$ 和 $v_i$ ,权值为 $a_i$ 和 $b_i$ 。
点的编号为 $0\sim n-1$ 。
输出格式
假设你求出的生成树为 $T$ ,你需要输出一行两个整数,分别为 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 。
如果有多解,请输出 $\displaystyle\sum_{e\in T}a_e$ 最小的那个。
输入输出样例
输入样例 #1
4 5
0 1 1 2
0 2 2 3
0 3 1 5
1 3 3 4
2 3 1 3
输出样例 #1
3 10
说明
对于 $100\%$ 的数据,$1\leq n\leq 200,1\leq m\leq 10000,0\leq a_i,b_i\leq 255$ 。