Background

问题描述

某公司要处理一个周期性的物流问题。 　　有n个城市，
第i个城市在每周的第j(1≤j≤7) 天会生产aij吨某种货物，
同时需要消耗bij吨该种货物。已知每周的产量等于消耗量（即aij之和等于bij之和）。 　　
城市之间有m条道路，第k条道路连接了城市sk和tk。一条道路上运输1吨货物有一个固定的成本ck。
道路都可以双向使用。每天运输的货物量没有限制。城市之间的距离并不远，
货物可以从任意一个城市运输到任意另一个城市并且在当天到达。 　　货物如果在当天没有被消耗掉
就需要存放在仓库里过夜。第i个城市的仓库容量为vi
，存放1 吨货物过一夜所需的成本是wi。 　　
请你计算该公司如果每周循环性地按照一个固定的流程调度货物的话
，该公司在最优方案下每周需要为货物的运输和存储消耗多少成本。
输入格式 　　
输入的第一行有两个正整数n和m，即城市的个数和道路的条数。 　　
接下来有n行，每行包含16个整数，用以描述第i个城市的相关数据。其中第i行包含的数为ai1, ai2, ai3, ai4, ai5, ai6, ai7, bi1, bi2, bi3, bi4, bi5, bi6, bi7, vi, wi。 　
　接下来有m行，每行包含3个整数，用以描述一条道路的相关数据。其中第k行包含的数为sk, tk和ck。 　
　输入数据中城市的编号均为1到n之间。
输入数据的每行的行首行尾均保证没有空格，两个数之间恰好被一个空格隔开。
输出格式 　　你只需要输出一个数，即最优方案下每周的支出。

样例输入

3 3
0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 4
0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 1
0 0 0 0 0 0 0 0 0 3 0 0 0 0 2 5
1 2 1
1 3 5
2 3 1

样例输出

67

样例说明

城市1 每周五生产5 吨货物，
把其中2 吨运到存储费用低廉的城市2 存储，
把1 吨运到城市3 存储，剩下的2 吨留在城市1。 　　在次周一的时候城市2 会消耗掉存放在那里的2 吨货物。
为了节约存储成本，
将囤放在城市1 的货物运到城市2 存放。周三再将所有货物运到城市3 以满足该城市的需求。 　　在此方案下，
每周的运输成本为8，
每周的存储成本为59，因此每周的总支出为67。 评测用例规模与约定 　　对于100%的数据，1≤n≤100，1≤m≤500，0≤aij,bij,vi≤100，1≤wi,ck≤100。

问题简述：（略）

问题分析：参考链接中的第一个和第二个是100分解题代码，第三个是90分。

程序说明：（略）

题意

在由n个节点组成的无向图中，AB边的权值C代表，从A到B运输每吨需要的费用。一些节点生产货物，一些节点接收货物（就像快递一样，一方发货一方收货），但是又存在区别，这里默认发货站点能够将货物在当日送达收货站点，但是虽然你可以送到我这里，真正来收获的人预订好是某个时间（周一到周日来计算）来取货，可能要过几天来取，这就出现了暂存费用，每个站点的暂存费用不一样，而且每个站点空间有限只能存v吨货物，题目要求所有货物送达费用和路途中暂存费用的总费用达到最少。

题解

大致读懂题意，感觉应该和费用流有关系，出现了每个站点存储空间限定（相当于流量限制），每个站点每吨存储费用（相当于单位流量的费用），接下进一步思考如何建图：起点与终点，很明显是所有发货站点与所有收获站点，用一个超级源点与超级终点连接即可；为了很好体现以天为单位的存储流量与费用，将每个站点分成七份，每一天一份，从第一天转移到第二天，只需要将这两个点连起来赋予流量与费用即可，每个点这样处理一遍，这样就将时间加进去了；站点间运送：流量无限，费用为边权。最后跑一遍ZKW费用流即可，100分。O(n^2m)

Limitation

1s, 1024KiB for each test case.