題目背景
小 G 有一群好朋友，他們經常互相借錢，
題目描述
假如說有三個好朋友 A，B，C，A 欠 B \(20\) 元，B 欠 C \(20\) 元，總債務規模為 \(20+20=40\) 元，
小 G 是個追求簡約的人，他覺得這樣的債務太繁雜了，他認為，上面的債務可以完全等價為 A 欠 C \(20\) 元，B 既不欠別人，別人也不欠他，這樣總債務規模就壓縮到了 \(20\) 元，
現在給定 \(n\) 個人和 \(m\) 條債務關系，小 G 想找到一種新的債務方案，使得每個人欠錢的總數不變，或被欠錢的總數不變（但是物件可以發生變化），并且使得總債務規模最小，
輸入格式
第一行兩個數字 \(n\)、\(m\)，含義如題目所述，
接下來 \(m\) 行，每行三個數字 \(a_i\)、\(b_i\)、\(c_i\)，表示 \(a_i\) 欠 \(b_i\) 的錢數為 \(c_i\)，
注意，資料中關于某兩個人 A 和 B 的債務資訊可能出現多次，將其累加即可， 如 A 欠 B \(20\) 元、A 欠 B \(30\) 元、B 欠 A \(10\) 元，其等價為 A 欠 B \(40\) 元，
輸出格式
輸出檔案共一行，輸出最小的總債務規模，
資料范圍
評測時間限制 \(1000\ \textrm{ms}\)，空間限制 \(128\ \textrm{MiB}\)，
- 對于 \(30\%\) 的資料，\(1\le n\le 10\)，\(1\le m\le 10\)；
- 對于 \(60\%\) 的資料，\(1\le n\le 100\)，\(1\le m\le 10^4\)；
- 對于 \(80\%\) 的資料，\(1\le n\le 10^4\)，\(1\le m\le 10^4\)；
- 對于 \(100\%\) 的資料，\(1\le n\le 10^6\)，\(1\le m\le 10^6\)，
對于所有的資料，保證 \(1\le a_i,b_i\le n\)，\(0<c_i\le 100\)，
分析
這道題的資料范圍和輸出形式，都指向了一個可能的方案，而我們的任務就是去證明，
\(100\ \texttt{pts}\)
我們先來考慮一個比較簡單的情況：
- A 欠 B \(1\) 塊錢；
- B 欠 A \(1\) 塊錢，
這樣，我們就能夠抵消掉，
這就是這個模型的第一個性質，我們不妨稱其為抵消法則，
同樣地，如果
- A 欠 B \(1\) 塊錢；
- B 欠 C \(1\) 塊錢，
則 A 欠 C \(1\) 塊錢，這就可以稱為繼承法則，
這就是這個模型的全部嗎？并不是，比如這個情況：
- A 欠 B \(2\) 塊錢；
- B 欠 A \(1\) 塊錢，
這不是用一個抵消法則能夠解決的，我們還要加入一種分裂法則，即 A 欠 B \(2\) 塊錢可以變成兩個 A 欠 B \(1\) 塊錢，
這下子問題似乎變得很復雜，但是我們將一個問題的核心法則抽象出來了，這樣就可以自動屏蔽掉很多無關資訊，
我們利用這些法則和常識，發現了一個比較有可能是可以的方法：
- 初始每個人都有一個資產值 \(v_i\)，賦為 \(0\)；
- 每發生一次借債 \(\left<a_i,b_i,c_i\right>\)，借債方 \(a_i\) 的資產加上 \(c_i\)，還債方 \(b_i\) 的資產減去 \(c_i\)；
- 最后的答案就是 \(\large{\sum\limits_{v_i>0}v_i}\) 或 \(\large{\left|\sum\limits_{v_i<0}v_i\right|}\)，
這個方法看似沒問題（雖然的確沒問題），但是嚴格的數學證明是不可少的，我們要證明兩件事：
- 最優性，即不可能有比這個方案還要小的債務規模，
- 可行性，則必然存在一種借債方案，使得這樣的債務規模可以實作，
最優性很好證明，
首先，對于任意的債務方案，最后的「資產」一定不變，這是很好證明的，利用幾個法則就能夠輕易推出，
則肯定不會存在一種方案，比直接利用最后資產倒推的方案來得好，這就是「最終資產」的不變性決定的，
那么，這一種所謂的方案又應該如何去構造呢？實際上很好解決，
我們可以將欠債（即「資產」為負）的人放在一起，而債主（「資產為正」的）放在一起，
然后我們可以對兩邊分別列出一個順序，就像這樣：
然后，我們將兩邊的第一個連起來，構造一個債務關系，
比如這個情況，我們就能夠在 -3 和 +1 之間建立債務關系，-3 要還 +1 \(1\) 塊錢，
此時，+1 心滿意足地走了，場地變成這個樣子：
我們只要一直這樣，就能不停地縮小債務規模，這樣遞回求解就能夠構造出一個方案，易證這是最優的，
Code
代碼十分簡單，不用過多注釋，
// @author 5ab
#include <cstdio>
#include <cctype>
using namespace std;
const int max_n = 1000000;
int cnt[max_n] = {};
inline int read()
{
int ch = getchar(), n = 0, t = 1;
while (isspace(ch)) { ch = getchar(); }
if (ch == '-') { t = -1, ch = getchar(); }
while (isdigit(ch)) { n = n * 10 + ch - '0', ch = getchar(); }
return n * t;
}
int main()
{
int n = read(), m = read(), ta, tb, tc, ans = 0;
for (int i = 0; i < m; i++)
{
ta = read() - 1, tb = read() - 1, tc = read();
cnt[ta] -= tc;
cnt[tb] += tc;
}
for (int i = 0; i < n; i++)
if (cnt[i] > 0)
ans += cnt[i];
printf("%d\n", ans);
return 0;
}
后記
這道題的關鍵反而是生活常識，沒有生活常識可能會較難作出此題，
所以，OI 也不能過度脫離生活，有時是生活給 OI 靈感，有時是 OI 給生活動力，OI 并不獨立于生活，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199354.html
標籤：其他