#P18780. [Kaist2021]Utilitarianism 2
[Kaist2021]Utilitarianism 2
Utilitarianism 2
题目描述
有 个疫苗生产商、 家医院和 名运输代理,分别从 开始编号。第 名代理可以从生产商 向医院 运送 份疫苗。任意两名代理对应的生产商、医院组合都不同。
每个生产商至多使用一名代理,每家医院也至多接收一名代理的运输。允许不选择某些生产商、医院或代理;选中的代理会运送其指定的全部疫苗。
对于一个代理集合 ,令 表示仅允许使用 中的代理时,在上述限制下最多能够运送的疫苗数量。设 为全部代理组成的集合,第 名代理的社会价值定义为
也就是说,在大家始终选择最优运输方案的前提下,该代理退出所造成的最大运输量损失,就是其社会价值。请计算每名代理的社会价值。
输入格式
第一行三个整数 。
接下来 行,第 行三个整数 ,描述第 名代理的任务。
输出格式
输出 行,第 行一个整数,表示第 名代理的社会价值。
数据范围
- 。
- 。
- ,,。
- 不同代理的 互不相同。
样例 1
输入
5 5 7
1 4 3
5 1 7
2 2 8
3 5 2
4 3 8
2 3 6
5 4 9
输出
1
1
8
2
8
0
0