惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

罗磊的独立博客
L
LangChain Blog
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
H
Hackread – Cybersecurity News, Data Breaches, AI and More
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
M
MIT News - Artificial intelligence
N
Netflix TechBlog - Medium
Vercel News
Vercel News
D
DataBreaches.Net
Microsoft Azure Blog
Microsoft Azure Blog
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
The Cloudflare Blog
U
Unit 42
阮一峰的网络日志
阮一峰的网络日志
Blog — PlanetScale
Blog — PlanetScale
Cloudbric
Cloudbric
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
Microsoft Security Blog
Microsoft Security Blog
月光博客
月光博客
I
InfoQ
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
Hugging Face - Blog
Hugging Face - Blog
Security Latest
Security Latest
T
Threatpost
GbyAI
GbyAI
K
Kaspersky official blog
S
SegmentFault 最新的问题
Schneier on Security
Schneier on Security
V
V2EX
W
WeLiveSecurity
Recorded Future
Recorded Future
WordPress大学
WordPress大学
L
LINUX DO - 最新话题
O
OpenAI News
Y
Y Combinator Blog
Google DeepMind News
Google DeepMind News
The Last Watchdog
The Last Watchdog
有赞技术团队
有赞技术团队
Attack and Defense Labs
Attack and Defense Labs
N
News | PayPal Newsroom
H
Help Net Security
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Webroot Blog
Webroot Blog
酷 壳 – CoolShell
酷 壳 – CoolShell
T
Troy Hunt's Blog
腾讯CDC
Scott Helme
Scott Helme
P
Privacy & Cybersecurity Law Blog
Recent Commits to openclaw:main
Recent Commits to openclaw:main
E
Exploit-DB.com RSS Feed

博客园 - zy_nic

SRM 424 div1 900 ProductOfPrices 翻译 .. emacs的c++mode contest contest 我的2-sat模板 Solution to GCJ Practice Contest Problem C, Cycles 约瑟夫问题的数学方法 我的模板 图的应用 pku3411 今天的比赛 死老鼠安装成功 pku3141 先帖个题目上来 hnu 11028 hnu 11015 joj 儿死三八 pku 1273
关于建图的
zy_nic · 2007-09-23 · via 博客园 - zy_nic

有N个机器(1…N),有M(1…M)件工作需要完成。并不是每个机器都能完成所有的工作,也就是说,每个机器只能完成某一些的工作。如果在第i台机器上完成t件工作,那么需要的花费是 cost[i] * t*t。

现在告诉你每台机器可以完成的工作编号,以及每台机器的cost。请你计算出完成所有的工作需要的最小的代价

这题如果话费是cost[i]*t的话,那么,如果i能完成j号任务,那么就连i到j的边,容量为1,费用为cost[i]  然后加入源点s,s到每个机器的流量为inf,每台机器到汇点t的容量为1,最后求s到t的最小费用最大流就可以了。

可是费用是cost[i]*t*t

t*t=1+3+5+7+9+……+(2*t-1)

如果第i台机器能够完成k项任务那么就把他分成k个点 从源点到 Dik的费用定义为 (2*k-1),容量为1,后面的建图方式如上

最后还是求s到t的最小费用最大流即可