A13154 | Decreasing Debts
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
There are $n$ people in this world, conveniently numbered $1$ through $n$ . They are using burles to buy goods and services. Occasionally, a person might not have enough currency to buy what he wants or needs, so he borrows money from someone else, with the idea that he will repay the loan later with interest. Let $d(a,b)$ denote the debt of $a$ towards $b$ , or $0$ if there is no such debt.
Sometimes, this becomes very complex, as the person lending money can run into financial troubles before his debtor is able to repay his debt, and finds himself in the need of borrowing money.
When this process runs for a long enough time, it might happen that there are so many debts that they can be consolidated. There are two ways this can be done:
1. Let $d(a,b) > 0$ and $d(c,d) > 0$ such that $a \neq c$ or $b \neq d$ . We can decrease the $d(a,b)$ and $d(c,d)$ by $z$ and increase $d(c,b)$ and $d(a,d)$ by $z$ , where $0 < z \leq \min(d(a,b),d(c,d))$ .
2. Let $d(a,a) > 0$ . We can set $d(a,a)$ to $0$ .
The total debt is defined as the sum of all debts:
$$$$\Sigma_d = \sum_{a,b} d(a,b) $$$$
Your goal is to use the above rules in any order any number of times, to make the total debt as small as possible. Note that you don't have to minimise the number of non-zero debts, only the total debt.
Sometimes, this becomes very complex, as the person lending money can run into financial troubles before his debtor is able to repay his debt, and finds himself in the need of borrowing money.
When this process runs for a long enough time, it might happen that there are so many debts that they can be consolidated. There are two ways this can be done:
1. Let $d(a,b) > 0$ and $d(c,d) > 0$ such that $a \neq c$ or $b \neq d$ . We can decrease the $d(a,b)$ and $d(c,d)$ by $z$ and increase $d(c,b)$ and $d(a,d)$ by $z$ , where $0 < z \leq \min(d(a,b),d(c,d))$ .
2. Let $d(a,a) > 0$ . We can set $d(a,a)$ to $0$ .
The total debt is defined as the sum of all debts:
$$$$\Sigma_d = \sum_{a,b} d(a,b) $$$$
Your goal is to use the above rules in any order any number of times, to make the total debt as small as possible. Note that you don't have to minimise the number of non-zero debts, only the total debt.
输入格式
The first line contains two space separated integers $n$ ( $1 \leq n \leq 10^5$ ) and $m$ ( $0 \leq m \leq 3\cdot 10^5$ ), representing the number of people and the number of debts, respectively.
$m$ lines follow, each of which contains three space separated integers $u_i$ , $v_i$ ( $1 \leq u_i, v_i \leq n, u_i \neq v_i$ ), $d_i$ ( $1 \leq d_i \leq 10^9$ ), meaning that the person $u_i$ borrowed $d_i$ burles from person $v_i$ .
$m$ lines follow, each of which contains three space separated integers $u_i$ , $v_i$ ( $1 \leq u_i, v_i \leq n, u_i \neq v_i$ ), $d_i$ ( $1 \leq d_i \leq 10^9$ ), meaning that the person $u_i$ borrowed $d_i$ burles from person $v_i$ .
输出格式
On the first line print an integer $m'$ ( $0 \leq m' \leq 3\cdot 10^5$ ), representing the number of debts after the consolidation. It can be shown that an answer always exists with this additional constraint.
After that print $m'$ lines, $i$ -th of which contains three space separated integers $u_i, v_i, d_i$ , meaning that the person $u_i$ owes the person $v_i$ exactly $d_i$ burles. The output must satisfy $1 \leq u_i, v_i \leq n$ , $u_i \neq v_i$ and $0 < d_i \leq 10^{18}$ .
For each pair $i \neq j$ , it should hold that $u_i \neq u_j$ or $v_i \neq v_j$ . In other words, each pair of people can be included at most once in the output.
After that print $m'$ lines, $i$ -th of which contains three space separated integers $u_i, v_i, d_i$ , meaning that the person $u_i$ owes the person $v_i$ exactly $d_i$ burles. The output must satisfy $1 \leq u_i, v_i \leq n$ , $u_i \neq v_i$ and $0 < d_i \leq 10^{18}$ .
For each pair $i \neq j$ , it should hold that $u_i \neq u_j$ or $v_i \neq v_j$ . In other words, each pair of people can be included at most once in the output.
输入输出样例
输入 #1
3 2 1 2 10 2 3 5
输出 #1
2 1 2 5 1 3 5
输入 #2
3 3 1 2 10 2 3 15 3 1 10
输出 #2
1 2 3 5
输入 #3
4 2 1 2 12 3 4 8
输出 #3
2 1 2 12 3 4 8
输入 #4
3 4 2 3 1 2 3 2 2 3 4 2 3 8
输出 #4
1 2 3 15
In the first example the optimal sequence of operations can be the following:
1. Perform an operation of the first type with $a = 1$ , $b = 2$ , $c = 2$ , $d = 3$ and $z = 5$ . The resulting debts are: $d(1, 2) = 5$ , $d(2, 2) = 5$ , $d(1, 3) = 5$ , all other debts are $0$ ;
2. Perform an operation of the second type with $a = 2$ . The resulting debts are: $d(1, 2) = 5$ , $d(1, 3) = 5$ , all other debts are $0$ .
In the second example the optimal sequence of operations can be the following:
1. Perform an operation of the first type with $a = 1$ , $b = 2$ , $c = 3$ , $d = 1$ and $z = 10$ . The resulting debts are: $d(3, 2) = 10$ , $d(2, 3) = 15$ , $d(1, 1) = 10$ , all other debts are $0$ ;
2. Perform an operation of the first type with $a = 2$ , $b = 3$ , $c = 3$ , $d = 2$ and $z = 10$ . The resulting debts are: $d(2, 2) = 10$ , $d(3, 3) = 10$ , $d(2, 3) = 5$ , $d(1, 1) = 10$ , all other debts are $0$ ;
3. Perform an operation of the second type with $a = 2$ . The resulting debts are: $d(3, 3) = 10$ , $d(2, 3) = 5$ , $d(1, 1) = 10$ , all other debts are $0$ ;
4. Perform an operation of the second type with $a = 3$ . The resulting debts are: $d(2, 3) = 5$ , $d(1, 1) = 10$ , all other debts are $0$ ;
5. Perform an operation of the second type with $a = 1$ . The resulting debts are: $d(2, 3) = 5$ , all other debts are $0$ .
1. Perform an operation of the first type with $a = 1$ , $b = 2$ , $c = 2$ , $d = 3$ and $z = 5$ . The resulting debts are: $d(1, 2) = 5$ , $d(2, 2) = 5$ , $d(1, 3) = 5$ , all other debts are $0$ ;
2. Perform an operation of the second type with $a = 2$ . The resulting debts are: $d(1, 2) = 5$ , $d(1, 3) = 5$ , all other debts are $0$ .
In the second example the optimal sequence of operations can be the following:
1. Perform an operation of the first type with $a = 1$ , $b = 2$ , $c = 3$ , $d = 1$ and $z = 10$ . The resulting debts are: $d(3, 2) = 10$ , $d(2, 3) = 15$ , $d(1, 1) = 10$ , all other debts are $0$ ;
2. Perform an operation of the first type with $a = 2$ , $b = 3$ , $c = 3$ , $d = 2$ and $z = 10$ . The resulting debts are: $d(2, 2) = 10$ , $d(3, 3) = 10$ , $d(2, 3) = 5$ , $d(1, 1) = 10$ , all other debts are $0$ ;
3. Perform an operation of the second type with $a = 2$ . The resulting debts are: $d(3, 3) = 10$ , $d(2, 3) = 5$ , $d(1, 1) = 10$ , all other debts are $0$ ;
4. Perform an operation of the second type with $a = 3$ . The resulting debts are: $d(2, 3) = 5$ , $d(1, 1) = 10$ , all other debts are $0$ ;
5. Perform an operation of the second type with $a = 1$ . The resulting debts are: $d(2, 3) = 5$ , all other debts are $0$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted