#P1344. [USACO4.4] 追查坏牛奶 Pollutant Control
[USACO4.4] 追查坏牛奶 Pollutant Control
题目描述
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情:公司不小心发送了一批有三聚氰胺的牛奶。
很不幸,你发现这件事的时候,有三聚氰胺的牛奶已经进入了送货网。这个送货网很大,而且关系复杂。你知道这批牛奶要发给哪个零售商,但是要把这批牛奶送到他手中有许多种途径。
送货网由一些仓库和运输卡车组成,每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候,有必要保证它不被送到零售商手里,所以必须使某些运输卡车停止运输,但是停止每辆卡车都会有一定的经济损失。
你的任务是,在保证坏牛奶不送到零售商的前提下,制定出停止卡车运输的方案,使损失最小。
输入格式
第 行两个整数 、, 表示仓库的数目, 表示运输卡车的数量。仓库 代表发货工厂,仓库 代表有三聚氰胺的牛奶要发往的零售商。
第 行,每行 个整数 、 和 。其中 、 分别表示这辆卡车的出发仓库和目的仓库。 表示让这辆卡车停止运输的损失。
输出格式
两个整数 和 , 表示最小的损失, 表示在损失最小的前提下,最少要停止的卡车数。
4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80
60 1
提示
对于 的数据,满足 ,,,,。
题目翻译来自 NOCOW。
USACO Training Section 4.4