首页 > K取方格数
开通博客写题解
头像 19-大数据一班-杨文冠
发表于 2021-05-07 20:50:35
拆点后入点和出点两条（容量，边权）为的边求解最大流需要寻找所以一条增广路，为了费用之和最小，可以改用spfa寻找一条单位费用之和最小的增广路，每次在残余网络中跑最长路，直到找到最大流。这题不要求最大流，所以如果残余网络中得不到费用后可以直接退出。 MyCode: #include <bits/ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 louhc
发表于 2019-08-24 14:11:40
思路 费用流裸题.将每个点拆成入点和出点,入点与出点之间连边,容量为1,价值为该点的数.这样该点只能经过一次且经过会得到该数的代价.实际上每个格子能经过多次,但只能得到一次的代价,因此再连一条容量为,价值为0的边.然后源点向连边,向汇点连边,跑一遍最大费用最大流即可. 代码 #include< 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”