| 题目名称 | 2401. Time is Money |
|---|---|
| 输入输出 | timeismoney.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 20 |
| 题目来源 |
 TenderRun
于2016-07-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：19， 通过率：21.05% | ||||
 dzyo |
100 | 1.733 s | 0.26 MiB | C++ |
 TenderRun |
100 | 2.339 s | 0.62 MiB | C++ |
 Awson |
100 | 2.707 s | 0.46 MiB | C++ |
 imh |
100 | 2.908 s | 0.54 MiB | C++ |
 AAAAAAAAAA |
90 | 4.705 s | 0.43 MiB | C++ |
 %dalao% |
90 | 4.857 s | 2.60 MiB | C++ |
 niconicoqaq |
90 | 4.990 s | 0.77 MiB | C++ |
|
%dalao% |
90 | 5.083 s | 3.37 MiB | C++ |
|
dzyo |
65 | 2.665 s | 0.21 MiB | C++ |
|
dzyo |
65 | 2.720 s | 0.23 MiB | C++ |
| 关于 Time is Money 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
读不懂题的，这个就是最小乘积生成树的模板题，和HNOI2014 frame类似，那道题我也上传了
| ||||
timeismoney 100 points
Source code: timeismoney.c, timeismoney.cpp, timeismoney.pas
Input file: timeismoney.in
Output file: timeismoney.out
Time limit: 2 seconds
Memory limit: 64 MB
The NetLine company wants to offer broadband internet to N towns. For this, it suffices to construct
a network of N-1 broadband links between the towns, with the property that a message can travel
from any town to any other town on this network. NetLine has already identified all pairs of towns
between which a direct link can be constructed. For each such possible link, they know the cost and
the time it would take to construct the link.
The company is interested in minimizing both the total amount of time (links are built one at a time)
and the total amount of money spent to build the entire network. Since they couldn’t decide among
the two criteria, they decided to use the following formula to evaluate the value of a network:
SumTime = sum of times spent to construct the chosen links
SumMoney = sum of the money spent to construct the chosen links
V = SumTime * SumMoney
Task
Find a list of N-1 links to build, which minimizes the value V.
Description of input
The first line of input contains integers N – the number of towns and M – the number of pairs of
towns which can be connected. The towns are numbered starting from 0 to N-1. Each of the next M
lines contain four integers x, y, t and c – meaning town x can be connected to town y in time t and
with cost c.
Description of output
In the first line of output print two numbers: the total time (SumTime) and total money (Sum-
Money) used in the optimal solution (the one with minimal value V), separated by one space. The
next N-1 lines describe the links to be constructed. Each line contains a pair of numbers (x,y) describing
a link to be build (which must be among the possible links described in the input file). The
pairs can be printed out in any order. When multiple solutions exist, you may print any of them.
· 1 ≤ N ≤ 200
· 1 ≤ M ≤ 10 000
· 0 ≤ x,y ≤ N-1
· 1 ≤ t,c ≤ 255
· One test has M = N - 1
· 40% of the tests will have for each possible link t = c
Example
timeismoney.in timeismoney.out
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
279 501
2 1
0 3
0 2
3 4
注意测试数据中不要求输出方案。