| 题目名称 | 2626. 双核cpu |
|---|---|
| 输入输出 | cpu.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Mealy
于2017-03-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：17， 提交：30， 通过率：56.67% | ||||
 AAAAAAAAAA |
100 | 0.202 s | 17.38 MiB | C++ |
 核糖核酸 |
100 | 0.205 s | 11.98 MiB | C++ |
 Faller |
100 | 0.211 s | 58.30 MiB | C++ |
 Marvolo |
100 | 0.223 s | 42.65 MiB | C++ |
 甘罗 |
100 | 0.260 s | 42.65 MiB | C++ |
 sxysxy |
100 | 0.271 s | 0.63 MiB | C++ |
|
sxysxy |
100 | 0.280 s | 0.63 MiB | C++ |
 dddch01 |
100 | 0.335 s | 2.78 MiB | C++ |
 Ostmbh |
100 | 0.375 s | 57.91 MiB | C++ |
|
sxysxy |
100 | 0.422 s | 0.63 MiB | C++ |
| 关于 双核cpu 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题劲啊蜜汁双核...thread大法好
 rvalue
2017-03-06 19:20
4楼
| ||||
|
这样啊，原来可以直接双向边容量相等。
这样本来要加4条边变成了2条边。运行时间也相差不小 | ||||
|
回复 @_Itachi :
这俩本来就是给初学者的呀……刚开始学的时候还是有思考复杂度的吧  Mealy
2017-03-05 18:04
2楼
| ||||
|
这题基本和“为了博多”一样吗，改改输出就过了（当然你首先不要忘记改文件名）
 _Itachi
2017-03-05 17:01
1楼
| ||||
【题目描述】
有一个双核CPU，有N个程序模块需要处理，每个模块必须运行在该CPU的某个核上，每个模块在CPU两个核上运行的代价分别为Ai和Bi，另外有M对程序模块需要进行数据交换，如果这一对程序模块在同一个核上则不需额外花费代价，否则需要额外花费指定的代价。
如何将这N个程序模块安排在两个核上运行，使得总的花费最小。
【输入格式】
第一行有两个整数N,M， (1 ≤ N ≤ 20000, 1 ≤ M ≤ 200000) ，含义如上所述；
接下来有N行，每一行有两个整数Ai和Bi，表示模块i分别在两个核上运行所需花费的代价；
接下来有M行，每一行有三个整数a,b,w，表示如果模块a和模块b不在同一个核上运行的话需要额外花费w的代价，用来在两个模块间进行数据交换。
【输出格式】
输出只有一个整数，即最小代价。
【样例输入】
3 1
1 10
2 10
10 3
2 3 1000
【样例输出】
13
【提示】
【来源】
poj