若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1474: 4.4.2 Pollutant Control 追查坏牛奶

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,192

题目描述

你第一天接手光明牛奶公司就发生了一件倒霉的事情:公司不小心发送了一批坏牛奶。很不幸,你发现这件事的时候,坏牛奶已经进入了送货网。这个送货网很大,而且关系复杂。你知道这批牛奶要发给哪个零售商,但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成,每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些坏牛奶的时候,有必要保证它不被送到零售商手里,所以必须使某些运输卡车停止运输,但是停止每辆卡车都会有一定的经济损失。你的任务是,再保证坏牛奶不送到零售商的前提下,制定出停止卡车运输的方案,使损失最小。

输入

第一行: 两个整数M(0<=M<=1000)、N(2<=N<=32), N表示仓库的数目,M表示运输卡车的数量。仓库1代 表发货工厂,仓库N代表坏牛奶要发往的零售商。
第2..M+1行: 每行3个整数 Si, Ei, Ci. Si ,Ei表示这 辆卡车的出发仓库,目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失

输出

第1行两个整数c、t,c表示最小的损失,T表示要停止的最少卡车数。接下来t 行表示你要停止哪几条线路。如果有多种方案使损失最小,输出停止的线路最少的方案。

样例输入

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

样例输出

60 1 3

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Skip Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist