#P18780. [Kaist2021]Utilitarianism 2

[Kaist2021]Utilitarianism 2

Utilitarianism 2

题目描述

有 nn 个疫苗生产商、mm 家医院和 kk 名运输代理,分别从 11 开始编号。第 ii 名代理可以从生产商 aia_i 向医院 bib_i 运送 cic_i 份疫苗。任意两名代理对应的生产商、医院组合都不同。

每个生产商至多使用一名代理,每家医院也至多接收一名代理的运输。允许不选择某些生产商、医院或代理;选中的代理会运送其指定的全部疫苗。

对于一个代理集合 SS,令 f(S)f(S) 表示仅允许使用 SS 中的代理时,在上述限制下最多能够运送的疫苗数量。设 UU 为全部代理组成的集合,第 ii 名代理的社会价值定义为

f(U)−f(U∖{i}).f(U)-f(U\setminus\{i\}).

也就是说,在大家始终选择最优运输方案的前提下,该代理退出所造成的最大运输量损失,就是其社会价值。请计算每名代理的社会价值。

输入格式

第一行三个整数 n,m,kn,m,k。

接下来 kk 行,第 ii 行三个整数 ai,bi,cia_i,b_i,c_i,描述第 ii 名代理的任务。

输出格式

输出 kk 行,第 ii 行一个整数,表示第 ii 名代理的社会价值。

数据范围

  • 1≤n,m≤20001\le n,m\le2000。
  • 1≤k≤min⁡(8000,nm)1\le k\le\min(8000,nm)。
  • 1≤ai≤n1\le a_i\le n,1≤bi≤m1\le b_i\le m,1≤ci≤10121\le c_i\le10^{12}。
  • 不同代理的 (ai,bi)(a_i,b_i) 互不相同。

样例 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