USACO 4.4.2 环境保护调查污染源解答与分析

Pollutant Control 追查坏牛奶

译 by Twink

描述

作为你第一天接手三鹿牛奶公司的第一天事件, 公司不小心发送了一批含有三聚氰胺的牛奶. 不幸的是, 在 you 发现这件事时, 这批已经进入配送系统的含问题产品的牛奶就已经扩散到了整个配送网络中. 这个配送网络规模庞大且结构复杂. 为了确定将这批产品送达的目标零售商, 我们需要考虑如何选择哪些运输卡车停运以减少损失. 每个卡车都在各自固定的两个仓库之间单向运输产品, 因此我们需要构建一个最小顶点覆盖问题模型来解决这个问题. 通过计算每个可能运输路线（路径）及其对应的卡车集合（arc set）来确定哪些卡车应被停运. 通过这种方式, 在保证没有一条路径能够将含有问题产品送达目标 retailer 的情况下实现损失最小化; 同时最大化被保留的道路（道路），从而最大限度地减少运输成本和时间消耗.

格式

PROGRAM NAME : milk6

INPUT FORMAT :

第一行: 两整数N(2≤N≤32)、M(0≤M≤1000)，其中N代表存储库数量而M表示用于运输的车辆数目。存储库编号1对应于生产方工厂地址而存储库编号N则指定用于运送三聚氰胺牛奶至零售终端的位置。第二至第M+1行: 每行包含三个整数Si,Ei,Ci。其中Si与Ei分别表示某辆车