最新要闻
- 当前时讯:最高检发新文:NFT法律属性定调哪般?
- 天天日报丨黄桃+椰果!林家铺子双色水果罐头8罐仅19.9元
- 天天头条:比亚迪再掀桌子!新款汉DM-i冠军版上市:18.98万起合资还怎么玩
- 同事都说买高像素就对了 四款热门高像素全画幅相机推荐-天天百事通
- 微资讯!HTC U23 Pro发布:性价比这么低的手机不多了
- 世界热点评!日赚4亿还嫌多?移动联通电信现在和10年前日赚一样多:手机资费下降95%等
- 百度投资卡车整车研发商载合汽车科技_环球快讯
- 今日讯!3万多买钻戒如今只值2000元 网友称还是黄金保值:你会买钻戒吗?
- 60Hz显示器配120帧显卡是浪费?答案意外_世界即时看
- 最新资讯:包含多家中国造车新势力!马斯克预言一年内必有车厂倒闭
- 360 AIGC产品定名360智脑、360鸿图
- 三星量产12nm DDR5内存:功耗骤降23% 全球新视野
- 追讨欠款的有效期限是多久?欠钱不还电话不接微信不回怎么办?
- 快报:零跑汽车在杭州成立动力系统公司,注册资本1亿元
- 地球母亲怎么了?世界气象组织警告:未来五年全球气温将创新高-热头条
- 全球最新:知名女演员最新大片引争议 网友惊呼:这花有毒!
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
P1344 [USACO4.4] 追查坏牛奶 Pollutant Control (网络流)
P1344 [USACO4.4] 追查坏牛奶 Pollutant Control (网络流)
题目链接
目录- P1344 [USACO4.4] 追查坏牛奶 Pollutant Control (网络流)
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 题目大意
- 思路
- 分析
- code
- 双倍经验
- 思路
- code
- 后记
不会网络流的可以看这个
(相关资料图)
题目描述
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情:公司不小心发送了一批有三聚氰胺的牛奶。
很不幸,你发现这件事的时候,有三聚氰胺的牛奶已经进入了送货网。这个送货网很大,而且关系复杂。你知道这批牛奶要发给哪个零售商,但是要把这批牛奶送到他手中有许多种途径。
送货网由一些仓库和运输卡车组成,每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候,有必要保证它不被送到零售商手里,所以必须使某些运输卡车停止运输,但是停止每辆卡车都会有一定的经济损失。
你的任务是,在保证坏牛奶不送到零售商的前提下,制定出停止卡车运输的方案,使损失最小。
输入格式
第 \(1\) 行两个整数 \(N\)、\(M\),\(N\) 表示仓库的数目,\(M\) 表示运输卡车的数量。仓库 \(1\) 代表发货工厂,仓库 \(N\) 代表有三聚氰胺的牛奶要发往的零售商。
第 \(2\sim M+1\) 行,每行 \(3\) 个整数 \(S_i\)、\(E_i\) 和 \(C_i\)。其中 \(S_i\)、\(E_i\) 分别表示这辆卡车的出发仓库和目的仓库。\(C_i\) 表示让这辆卡车停止运输的损失。
输出格式
两个整数 \(C\) 和 \(T\),\(C\) 表示最小的损失,\(T\) 表示在损失最小的前提下,最少要停止的卡车数。
样例 #1
样例输入 #1
4 51 3 1003 2 502 4 601 2 402 3 80
样例输出 #1
60 1
提示
对于 \(100 \%\) 的数据,满足 \(2 \le N \le 32\),\(0 \le M \le 10^3\),\(1 \le S_i \le N\),\(1 \le E_i \le N\),\(0 \le C_i \le 2 \times 10^6\)。
题目大意
现在有一个有向图,每一条边有一个边权表示删除这条边需要的代价,问你怎么操作,使得 \(1\to n\)
没有路径相连且代价最小,同时要求删除的最少路径。
思路
显然,这是求一个图的最小割问题,我们知道最大流等于最小割,所以求出最小割即可。
此时可能有很多种方案,我们需要求出这些方案中的最少路径数。
我们可以把所有边都乘上一个 \(a\) (建议取 \(1007\) ),再 \(+1\) 。
此时最大流记为 \(ans\)
那么 \(c = ans / a\) ,\(T = ans \mod a\)
分析
我们把所有边权 \(*a+1\) 后,答案又 \(/a\) 当路径小于 \(a\) 时是不影响 \(C\) 的。
然后 因为我们 \(+1\) 了,所以最小路径数仍然是最小割,其他路径就比最小割要大,摸上 \(a\) 后就是 \(T\) 了。
code
#include #define LL long long#define fu(x, y, z) for (int x = y; x <= z; x++)using namespace std;const int N = 35, M = 1005, mod = 1007;const LL Max = 1e15;int n, m, d[N], vd[M], cnt = 1, hd[N];LL ans, ans1, p[M << 1];struct E { int to, nt, flg; LL w;} e[M << 1];void add(int x, int y, LL z) { e[++cnt].to = y, e[cnt].nt = hd[x], e[cnt].w = z, hd[x] = cnt; }LL dfs(int x, LL pt) { LL now = pt, del = 0; int y, mind = n - 1; if (x == n) return pt; for (int i = hd[x]; i; i = e[i].nt) { if (!e[i].w) continue; y = e[i].to; if (d[x] == d[y] + 1) { del = min(e[i].w, now); del = dfs(y, del); now -= del; e[i].w -= del, e[i ^ 1].w += del; if (d[1] >= n) return pt - now; if (!now) break; } mind = min(mind, d[y]); } if (now == pt) { vd[d[x]]--; if (!vd[d[x]]) d[1] = n; d[x] = mind + 1; vd[d[x]]++; } return pt - now;}LL flow() { LL sum = 0; fu(i, 1, n) d[i] = 0; vd[0] = n; while (d[1] < n) sum += dfs(1, Max); return sum;}int main() { int u, v; LL w; scanf("%d%d", &n, &m); fu(i, 1, m) { scanf("%d%d%lld", &u, &v, &w); p[cnt + 1] = w * mod + 1; add(u, v, w * mod + 1), add(v, u, 0); } ans = flow(); printf("%lld %lld\n", ans / mod, ans % mod); // for (int i = 2; i <= cnt; i += 2) { // fu(j, 2, cnt) if (!e[j].flg) e[j].w = p[j]; // e[i].w = 0; // ans1 = flow(); // if (ans1 + p[i] == ans) { // cout << i / 2 << "\n"; // e[i].flg = 1, e[i ^ 1].flg = 1, ans -= p[i]; // } // } return 0;}
双倍经验
[OJ](追查坏牛奶 - 题目 - DYOJ)
思路
要求输出方案。
也就是看看那条是满流边。
我们把这条边暂时删掉之后看看现在的答案记为 \(ans1\) ,边权记为 \(e[i].w\) 是否满足
\[ans1 + e[i].w = ans\]如果满足就是路径。
code
#include #define LL long long#define fu(x , y , z) for(int x = y ; x <= z ; x ++)using namespace std;const int N = 35 , M = 1005 , mod = 1007;const LL Max = 1e15;int d[N] , vd[M] , n , m , hd[N] , cnt = 1;LL ans , t , ans1 , p[M << 1];struct E { int to , nt , flg; LL w;} e[M << 1];void add (int x , int y , int z) { e[++cnt].to = y , e[cnt].nt = hd[x] , e[cnt].w = z , hd[x] = cnt; }LL dfs (int x , LL pt) { LL now = pt , del = 0; int mind = n - 1 , y; if (x == n) return pt; for (int i = hd[x] ; i ; i = e[i].nt) { if (!e[i].w) continue; y = e[i].to; if (d[x] == d[y] + 1) { del = min (now , e[i].w); del = dfs (y , del); now -= del; e[i].w -= del , e[i ^ 1].w += del; if (d[1] >= n) return pt - now; if (!now) break; } mind = min (mind , d[y]); } if (now == pt) { vd[d[x]] --; if (!vd[d[x]]) d[1] = n; d[x] = mind + 1; vd[d[x]] ++; } return pt - now;}LL flow () { LL sum = 0; vd[0] = n; fu (i , 1 , n) d[i] = 0; while (d[1] < n) { sum += dfs (1 , Max); } return sum;}int main () { int u , v; LL w; scanf ("%d%d" , &n , &m); fu (i , 1 , m) { scanf ("%d%d%lld" , &u , &v , &w); p[cnt + 1] = w * mod + 1; add (u , v , w * mod + 1) , add (v , u , 0); } ans = flow (); printf ("%lld %lld\n" , ans / mod , ans % mod); for (int i = 2 ; i <= cnt ; i += 2) { fu (j , 2 , cnt) if (!e[j].flg) e[j].w = p[j]; e[i].w = 0; ans1 = flow (); if (ans1 + p[i] == ans) { cout << i / 2 << endl; e[i].flg = 1 , e[i ^ 1].flg = 1 , ans -= p[i]; } } return 0;}
后记
原题检测真的恶心!!!
关键词:
-
P1344 [USACO4.4] 追查坏牛奶 Pollutant Control (网络流)
P1344[USACO4 4]追查坏牛奶PollutantControl(网络流)题目链接不会网络流的可以看这个题目描述你第一天接
来源: -
全球今日报丨【新华500】新华500指数(989001)18日下跌0.14%
新华500指数(989001)18日收盘跌0 14%,报4354 71点。指数盘中最高触及4384 16点,最低触及4336 77点,成
来源: P1344 [USACO4.4] 追查坏牛奶 Pollutant Control (网络流)
MySQL 迁移至 SQLite 问题记录 全球通讯
全球今日报丨【新华500】新华500指数(989001)18日下跌0.14%
当前时讯:最高检发新文:NFT法律属性定调哪般?
天天日报丨黄桃+椰果!林家铺子双色水果罐头8罐仅19.9元
天天头条:比亚迪再掀桌子!新款汉DM-i冠军版上市:18.98万起合资还怎么玩
同事都说买高像素就对了 四款热门高像素全画幅相机推荐-天天百事通
微资讯!HTC U23 Pro发布:性价比这么低的手机不多了
世界热点评!日赚4亿还嫌多?移动联通电信现在和10年前日赚一样多:手机资费下降95%等
百度投资卡车整车研发商载合汽车科技_环球快讯
环球热点![MySQL 如何分析性能]
天天速递!Python从零到壹丨图像增强的顶帽运算和底帽运算
知识拷问:工作站和服务器哪个更适合做CST电磁仿真?|每日观察
今日讯!3万多买钻戒如今只值2000元 网友称还是黄金保值:你会买钻戒吗?
60Hz显示器配120帧显卡是浪费?答案意外_世界即时看
最新资讯:包含多家中国造车新势力!马斯克预言一年内必有车厂倒闭
360 AIGC产品定名360智脑、360鸿图
三星量产12nm DDR5内存:功耗骤降23% 全球新视野
追讨欠款的有效期限是多久?欠钱不还电话不接微信不回怎么办?
ChatGPT 插件,组合后更妙了
快报:零跑汽车在杭州成立动力系统公司,注册资本1亿元
地球母亲怎么了?世界气象组织警告:未来五年全球气温将创新高-热头条
全球最新:知名女演员最新大片引争议 网友惊呼:这花有毒!
用这些C#代码混淆器保护你的代码安全_速递
环球微头条丨港元1个月拆息升至近5个月高 报4.57238厘
215英寸口袋巨幕!雷鸟Air Plus发布:首发2299元
世界快消息!男子在路边花5600元买到战国青铜剑:捐赠给博物馆
《王者荣耀》安琪拉/亚瑟520限定皮肤公布 传说品质-每日聚焦
周星驰担任网飞版《美猴王》执行制作:定档8月18日 大圣外形被吐槽|世界速讯
《权力的游戏》演员称曾被网暴到退网:就因为角色不讨喜
5月18日河北中昌化肥硫酸铵价格动态
世界最资讯丨MongoDB + SpringBoot 的基础CRUD、聚合查询
开源即时通讯IM框架MobileIMSDK的Uniapp端开发快速入门
【世界独家】TimescaleDB VS TDengine:写入性能和查询性能是 TDengine 的 1/6、1/28
世界百事通!夜莺官方文档优化第一弹:手把手教你部署和架构讲解,消灭所有部署失败的 case!干!
直播预告 | 员工在公司体验感UP,原因竟然是这个......
美国债务上限谈判出现曙光 日元价格跌破年内新低
全球热点评!小米Civi 3首发天玑8200 Ultra!小米影像大脑更强了:连拍提速235%
报告称:81%员工不认为其工作可以被AI取代-天天热点
7450MB/s!三星990 Pro旗舰SSD价格腰斩:2TB只要1229元
每日时讯!发条朋友圈就能赚钱?支付宝辟谣:“朋友圈出租”是骗局
头条:魔兽国服关了114天 暴雪选择躺平:工作室脚本泛滥 玩家遭殃
国家金融监督管理总局官方微信公众号今日上线 世界讯息
《安富莱嵌入式周报》第312期:开源磁场照相机,仿生神经元PCB,开源无线耳机,手机系统PalmOS移植到各种单片机,开放系统组装协议OSAP 环球聚看点
今日精选:第141篇:微信小程序wx.request接口报错(errno: 600001, errMsg: "request:fail -2:net::ERR_
阿里云微服务引擎 MSE 全新升级,实用能力更普惠,最高降幅 75%
焦点信息:沉默的答案!直播源码禁言技术的实现
spring框架_常见工厂后处理器 最新资讯
预售价13.98-14.98万元 北京现代MUFASA定名沐飒 全球时讯
稻香村旗舰店:稻香私房粽子4只9.9元狂促(4粽4味)|今日快讯
天天百事通!Redmi Book 14轻薄本第三大升级公布:4000元档颜值绝了
一老年代步车当街起火:爷孙两人被严重烧伤
纯白YYDS!魅族20白色款3199元起开始预约:3年质保
女生遭两闺蜜PUA长达8年被骗百万 网友提醒:警惕“贬低式关系”
2023广州李荣浩演唱会需要预约吗?
全球热资讯!HTTP1.0、HTTP1.1、HTTP2.0 协议的特点
周杰伦好像被舞伴碰瓷 周杰伦表情一脸错愕(图)_环球时讯
环球关注:亚瑟首款传说皮肤 《王者荣耀》520皮肤今晚上架:打包250元 你买吗?
白嫖7万2!岚图追光四大选装包限时免费:入门即顶配_天天最资讯
对话不再“一次性”:BingChat新增聊天内容导出功能
一景区沙下埋20厘米三角钉 越野车轮胎被扎:官方通报调查结果 全球通讯
我国今年沙尘爆发原因找到了:蒙古国贡献超40% 冷锋、气旋天气主导
劳模登讲台 思政“活”起来
恶俗婚闹哪里最多_大家都见过哪些恶俗的婚闹-环球热门
全球新动态:Take-Two暗示《GTA6》明年问世
00后裸辞旅游被批 家里有矿吗:本人回应:享受当下 拒绝加班 焦点信息
3万元钻戒如今只值2千 越来越多新人告别智商税 婚礼用十几元道具戒指
热议:特斯拉花钱打广告 能加速马斯克上天吗?
华为手机麒麟新处理器曝光:搞定7nm工艺?
键凯科技05月17日被沪股通减持1.77万股 全球今日讯
Linux学习须牢记这几点|天天速看料
在岸、离岸人民币对美元汇率双双破“7” 专家:人民币不存在大幅贬值空间-世界微速讯
每日热点:把调研成果转化为改进工作实际举措
聚焦:华为5.5G助力 上海移动:2030年实现双万兆小区全覆盖
天天报道:9.4分你看没?腾讯:《漫长的季节》是5年来豆瓣评分最高本土剧
世界气象组织:有记录以来最热年要来了 全球气温推向未知领域 环球速看
热门中概股涨跌不一 腾讯音乐涨超8% 每日信息
两个电风扇放一起 就能使人窒息身亡?夏天这件事真的要注意 即时焦点
中国移动联合华为发布“云手机”:老爷机也能玩大型游戏
我所知道的Handler
百事通!解决xorm逆向工程问题
小事记 | 龙光清盘呈请聆讯押后 华夏幸福下属公司列为失信被执行人_播资讯
上映1天票房破亿!美国大片《速度与激情10》豆瓣7.0分:巨石强森惊喜彩蛋|快看
年轻人第一辆插混SUV来了!深蓝S7将于5月20日开订:20万内最帅最能打?
世界报道:解决《王国之泪》掉帧严重 Switch超频教程来了 稳定30帧运行
华为、小米、OPPO、vivo联手:快充终于要统一了?!
男子暴饮暴食后血液滤出400毫升油脂:甘油三酯严重超标|每日精选
是故学然后知不足断句_是故学然后知不足
整式的乘除计算题及答案_整式的乘除计算题
网友模仿《漫长的季节》秦昊食谱 导致将自己送进医院引发热议
任天堂Switch平台《塞尔达传说:王国之泪》上市三天取得好成绩 销量破千万
索尼将于5月25日举行新一期游戏发布会 市场高达一个小时
特斯拉考虑在印度建立一家汽车制造工厂 未讨论降低电动汽车进口关税
Steam Deck掌机因振动反馈技术惹上麻烦 Valve遭到起诉
《王者荣耀》蝉联2023年4月全球手游畅销榜冠军 新角色姬小满登场
演员许娇晒出泳装照引发网友热议 正面回复称大大方方展示
电影《变形金刚7》发布全新海报 中国内地正式定档6月9日上映
日本最大网络广告代理商推出日语最大级别AI语言模型 可商业使用
童年回忆《知音漫客》将于今年5月至10月之间休刊 曾连载众多知名作品
世界观天下!管理好一个团队的方法(这样管理好一个团队)