其实我们发现一个人欠债跟债主是谁没关系 因为总和是不变的
然后根据题目给出的操作 我们希望账面数字尽量小
于是我们每次随便选一正一负 让正的借钱给负的 这样账面数字就会减小
于是贪心选取即可 其实也不是贪心 可以说是任意选取
复杂度$O(n)$
比赛的时候陷入思维误区 不断向图论方向想 得出跟这差不多的结论 但是必须在一个联通块里 于是我的想法还需要查询一个联通块里正负的值 然后就爆炸了
其实因为欠债跟债主没什么关系 只要你欠债了 并且总数没有出错 那么关系总是不会出错的 所以在不在联通块里其实不重要
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e5 + 5; struct node { int u, v; ll w; node() = default; node(int _u, int _v, ll _w) : u(_u), v(_v), w(_w) {} }; int n, m; ll d[maxn]; int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= m; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); d[u] -= w; d[v] += w; } vector<node> ans; for(int i = 1, j = 1; i <= n; ++i) { while(d[i] > 0) { while(j <= n && d[j] >= 0) { ++j; } ll delta = min(d[i], -d[j]); d[i] -= delta; d[j] += delta; ans.push_back(node(j, i, delta)); } } printf("%d\n", ans.size()); for(auto x : ans) { printf("%d %d %lld\n", x.u, x.v, x.w); } return 0; }
原文：https://www.cnblogs.com/19992147orz/p/12064469.html
