假设一群朋友去度假，有时他们互相借钱。例如，阿米特(Amit)为比克兰(Bikram)的午餐支付了10美元。后来，钱丹(Chandan)给阿米特(Amit)5美元作为出租车费。我们必须设计一个模型，其中每笔交易都作为一个元组(x,y,z)，这意味着人x给人y $ z。
假设Amit，Bikram和Chandan分别是人0、1和2，则交易可以表示为[[0，1，10]，[2，0，5]]。如果我们有一组人之间的交易列表，那么我们必须找到清算债务所需的最小交易数。
因此，如果输入类似于[[0,1,10]，[2,0,5]]，则输出将为2，因为人#0给人#1 $ 10。然后人#2给人# 0 $ 5。这里需要进行两次交易。一种解决债务的方法是#1人向#0人和#2人支付5美元。
为了解决这个问题，我们将遵循以下步骤-
定义数组v
定义一个函数dfs()，它将使用idx，
ret：= inf
while（idx <v的大小，而不是v [idx]为非零），执行-
（将idx增加1）
对于初始化i：= idx + 1，当i-v的大小时，更新（将i增加1），执行-
v [i]：= v [i] + v [idx]
ret：= ret的最小值和1 + dfs（idx + 1）
v [i]：= v [i]-v [idx]
如果v [i] * v [idx] <0，则-
返回（如果ret与inf相同，则为0，否则为ret）
从主要方法中执行以下操作-
定义一张映射
n：= t的大小
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
u：= t [i，0]，v：= t [i，1]
bal：= t [i，2]
m [u]：= m [u] + bal
m [v]：= m [v]-bal
对于m中的每个键值对i，执行-
在v的末尾插入i的值
如果i的值，则-
（将i增加1）
返回dfs的最小值和v的大小
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> v;
int dfs(int idx) {
int ret = INT_MAX;
while (idx < v.size() && !v[idx])
idx++;
for (int i = idx + 1; i < v.size(); i++) {
if (v[i] * v[idx] < 0) {
v[i] += v[idx];
ret = min(ret, 1 + dfs(idx + 1));
v[i] -= v[idx];
}
}
return ret == INT_MAX ? 0 : ret;
}
int minTransfers(vector<vector<int>>&t) {
map<int, int> m;
int n = t.size();
for (int i = 0; i < n; i++) {
int u = t[i][0];
int v = t[i][1];
int bal = t[i][2];
m[u] += bal;
m[v] -= bal;
}
map<int, int>::iterator i = m.begin();
while (i != m.end()) {
if (i->second)
v.push_back(i->second);
i++;
}
return min(dfs(0), (int)v.size());
}
};
main() {
Solution ob;
vector<vector<int>> v = {{0,1,10},{2,0,5}};
cout << (ob.minTransfers(v));
}{{0,1,10},{2,0,5}}输出结果
2