NOI 2008 employee 招募一批志愿者,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。用尽量少的费用招募足够的志愿者.

Slides:



Advertisements
Similar presentations
月經異常的原因及警訊 組員: 陳少康、張康樂、許晉愷、何曄、方泠瑩、張 顓麟、蘇梓喬、溫鵬皓、林雅雯.
Advertisements

說明事項  大陸交換學習近況  大陸姐妹校介紹  申請資格和程序  研究生補助 大陸交換學習近況 2009 年秋首次進行,計有 6 校共 20 位學生來校交換學習。 來校交換生.
消失的吸管 隊名:吸管應該消失才隊.
兵车行 杜甫 福州十一中语文组 林嵘臻.
助學工作說明會 及 教育訓練.
窦娥冤 关汉卿 感天动地 元·关汉卿.
第十五章 控制方法.
小猪.
報告書名:父母會傷人 班級:二技幼四甲 姓名:吳婉如 學號:1A2I0034 指導老師:高家斌
師資生修讀教育學程 重點提醒 師資培育暨就業輔導中心.
文書檔案組Q&A 崇右技術學院 文書檔案組 Q & A 總務處.
公職人員財產信託簡介 第一銀行信託處 編製.
综合实践活动 设计与实践案例 ——《感恩父母》主题班会.
經分表聘用兼任助理流程 完成 新增/修改 經分表 計畫無聘任兼任助理(新增) 紙本送所屬單位審核 計畫聘任兼任助理(新增)
关于市场营销的分析 ——以九阳豆浆机为例 品牌经营——让每一个家庭都拥有一台九阳豆浆机 营销管理——采取文化、概念、网络等营销组合
未婚懷孕:你想清楚了嗎 瑞芳國中 林碧欣.
國科會經費報銷說明 報告人:陳秀合 分 機: 年11月 12日(一).
手太阳小肠经.
媽,我們真的不一樣 青少年期與中年期 老師: 趙品淳老師 組員: 胡珮玟4A1I0006 馬菀謙4A1I0040
課室經營-老師實務分享 課程名稱:幼兒園課室經營 指導老師:李芳靜 組員:1A3I0004蔡雨潔1A3I0009鄭益秀
實用技能學程答客問 Q&A 大明高中附設進修學校 教導處 編製.
知其不可而为之.
中国画家协会理事、安徽省美术家协会会员、 工艺美术师、黄山市邮协常务理事余承平主讲
畜牧類天然災害查報 及救助作業簡介 臺南市政府農業局畜產科 李東仁 臺南市政府農業局畜產科.
氣喘 組別:第一組 組員: 4A 蔡易儒 4A1I0026 鄭筠蒨 4A1I0034 韓宜瑄 4A1I0035 劉毓眉
財團法人台北市任兆璋修女林美智老師教育基金會
游泳四式技術分析暨初級教法.
100學年度719班 親師懇談.
第五章 策划用文体写作.
班級:二幼三甲 姓名:郭小瑄 、 詹淑評 學號:1A2I0029 、1A2I0025
社團資料製作 亞東技術學院課外組 岳擎天
道路、管線事故緊急應變處理課程.
解放軍論壇 中共信息戰發展 對我國軍事戰略之影響.
指導老師:陳韻如 姓名:吳宜珊 學號:4A0I0911 班級:幼保二乙
財團法人台北市任兆璋修女林美智老師教育基金會
汉字的构造.
诵读欣赏 古代诗词三首.
授课教师简历 刘付才,男,中学高级教师,亳州一中南校体 育教研组长,全国体育优质课一等奖获得者,华佗 五禽戏第五十八代传承人;长期从事五禽戏教学和 研究工作,参与创编了国家级课题“校园五禽戏”; 2014年全国学生运动会展示中获得优秀表演奖; 2015年指导的五禽戏传人进行的五禽戏教学获得全 国一等奖,编著的《华佗五禽戏之简易健身操》即.
花的構造- (資料參考--鄭元春 植物Q&A一書) 花瓣 花萼 雌蕊 雄蕊.
認識股票 認識股票.
103年度身心障礙福利機構評鑑 日間及住宿機構指標說明 ~會計及財務管理~
洪涝灾害重点传染病的预防 江苏省疾病预防控制中心 汪华.
专题五 高瞻远瞩 把握未来 ——信息化战争 主讲教师:.
屏東縣政府對民間團體補助經費作業要點 & 簡易計畫書撰寫概要與核銷注意事項
--洲仔尾的鹼菜 與櫻桃鴨的結合-- 鴨賞的故事.
第十章 现代秘书协调工作.
小 桔 灯 市场赢利能力与战略 主讲:杨贤耀.
傳統童玩遊戲創新 組別:第八組 班級:幼保二甲 組員: 4A0I0005柯舒涵 4A0I0011謝孟真
戲水安全.
践行新时期广东精神 推进广东公路文化繁荣与发展 ——关于广东省公路文化建设与实践的思考
外僑扣繳實務講習 1.
職場性騷擾相關法 律責任-以上司對 下屬性騷擾為例
贴近教学 服务师生 方便老师.
六年级 语文 下册 第四单元 指尖的世界.
敬业与乐业.
(浙教版)四年级品德与社会下册 共同生活的世界 第四单元 世界之窗 第二课时.
题型复习.
主講人:曲軒 協理 就業情報資訊 日期:2003年5月8日
衛生筷,衛生嗎? 綠的關懷協會 常務理事 董雅坋.
高粱酒香-金門城.
讀報教育 報告者:施子慧 資料來源:徐瑞美、施子慧.
103年度 健康促進學校輔導與網站維護─ 「臺灣健康促進學校之網站特色介紹」 張子超 教授
107年勞動基準法修法重點解析 高雄市政府勞工局.
國立中山大學管理學院 國際人才培育中心 大專人才培訓就業學程.
西师大版语文五年级上册第七单元 心田上的百合花.
開課單位作業流程及Q&A 開啟衛生署積分系統首頁 畫面如下頁.
精算假設品質的基本要求 精算假設應提出明確的假設數值,同時應提供實際經驗率資料以作為假設訂定之依據,且精算人員應說明實際經驗率與假設數值間的合理關係。 精算假設若由其他單位提供(例如:利率或投資報酬率假設由投資部門提供),精算人員仍應了解其假設的方法,並就其假設合理性及假設方法提出意見。 精算假設若與前一年相較有所變更時,精算人員應說明假設改變的原因,對於有改變的精算假設數值宜列對照表比較並說明。精算人員應評估假設的改變對財務影響是否顯著,若顯著則應提供量化數值以說明其影響程度。
臺南市 107學年度 國中生志願選填試探與輔導知能研習
Xián 伯 牙 绝 弦 安徽淮南市八公山区第二小学 陈燕朵.
Presentation transcript:

NOI 2008 employee 招募一批志愿者,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。用尽量少的费用招募足够的志愿者

费 用 流 朱秋明 2015年8月

费用(代价) 容量 C 代价 b 注:反向边的代价为正向边的负数

1、 连续最短路算法(Successive Shortest Path); 2、 消圈算法(Cycle Canceling); 3、 原始对偶算法(Primal Dual); 4、 网络单纯形(Network Simplex)。 (5、 ZKW算法)

连续最短路算法 SPFA

消圈法 消圈定理:残留网络里如果存在负费用圈,那么当前流不是最小费用流。 负圈:费用总和是负数,且每条边的剩余流量大于0

POJ 2175 有n座建筑物,每个建筑物里面有一些人,城市里面建了m座避难所。每座避难所只能容纳有限人数。 给出每个建筑物和避难所的坐标(曼哈顿距离+1)。现在给出一种避难方案,问这种方案是否为最优方案,如果不是,请输出一种比当前更优的方案(不一定最优)。

“请输出一种比当前更优的方案(不一定为最优)” 建图? “请输出一种比当前更优的方案(不一定为最优)”

1、建立残留网 2、SPFA找负圈

[SCOI2007]修车 同一时刻有N位车主,维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 (顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。)

建图: 1、将每个技术员分为N个点(第k个点表示修完前k+1辆后修第k辆); 费用为:k * w(读入时间); 2、加入顾客,分别与技术员连边,容量为1; 3、加入源点、汇点,跑最小费用流。

NOI 2008 employee 招募一批志愿者,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。用尽量少的费用招募足够的志愿者

种类 1 2 3 4 5 时间 1-2 1-1 2-3 3-3 3-4 费用 6 设雇佣第i类志愿者的人数为X[i] 每个志愿者的费用为V[i] 第j天雇佣的人数为P[j]

P[3] = X[3] + X[4] +X[5] >= 5 P[4] = X[5] >= 3 ① P[1] - P[0] = X[1] + X[2] - Y[1] = 4 ② P[2] - P[1] = X[3] - X[2] -Y[2] +Y[1] = -2 ③ P[3] - P[2] = X[4] + X[5] - X[1] - Y[3] + Y[2] =3 ④ P[4] - P[3] = - X[3] - X[4] + Y[3] - Y[4] = -2 ⑤ P[5] - P[4] = - X[5] + Y[4] = -3

① - X[1] - X[2] + Y[1] + 4 = 0 ② - X[3] + X[2] + Y[2] - Y[1] - 2 = 0 ③ - X[4] - X[5] + X[1] + Y[3] - Y[2] + 3 = 0 ④ X[3] + X[4] - Y[3] + Y[4] - 2 = 0 ⑤ X[5] - Y[4] - 3 = 0

网络流的精髓: 建模

谢谢!

Q&A