| 题目名称 | 894. 追查坏牛奶 |
|---|---|
| 输入输出 | milk6.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 12 |
| 题目来源 |
 sywgz
于2012-07-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 查看题解 | 分享题解 |
| 通过：26， 提交：82， 通过率：31.71% | ||||
 真呆菌 |
100 | 0.003 s | 0.35 MiB | C++ |
 new ioer |
100 | 0.005 s | 0.31 MiB | C++ |
|
new ioer |
100 | 0.005 s | 0.32 MiB | C++ |
|
真呆菌 |
100 | 0.005 s | 0.38 MiB | C++ |
 Youngsc |
100 | 0.008 s | 0.31 MiB | C++ |
 苜 |
100 | 0.008 s | 3.28 MiB | C++ |
|
苜 |
100 | 0.009 s | 3.28 MiB | C++ |
 kxxy |
100 | 0.018 s | 0.41 MiB | C++ |
 HouJikan |
100 | 0.028 s | 0.29 MiB | C++ |
 QILIN |
100 | 0.031 s | 0.33 MiB | C++ |
| 关于 追查坏牛奶 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
字典序最小真是哔了狗了！
 _Itachi
2017-01-06 12:18
5楼
| ||||
|
割边数一样的话还要输出字典序最小的我真是哔了狗了
STL里的vector如果出现g[x].size()==0的话 你写for(int i=g[x]-1;~i;i--)它就抽了... ps:STL开了O2都是O(1)的我会乱说? update:我写的好像是错的QAQ | ||||
|
对智神的日常ym orzzzzzzzzzzzzzzzzzzz
真呆菌
2015-04-03 14:45
3楼
| ||||
|
求割边简直求成傻逼了。。
首先求最大流，然后将所有满流的边容量改成1，没有满流的改为INF，再求最大流就是答案。。 然后对于第二个图求割边 | ||||
|
爆int的最大流，你值得拥有！
| ||||
cstdio【题目描述】
你第一天接手光明牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批坏牛奶。很不幸，你发现这件事的时候，坏牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些坏牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，再保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
【输入格式】
第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), 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