UVA 538 - Balancing Bank Accounts

題目鏈接

題意：給定一些人的欠錢關系，要求在n-1次內還清錢，問方案

思路：貪心，處理出每一個人最后錢的狀態，然后直接每一個人都和最后一個人操作就可以

代碼：

      #include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
using namespace std;

const int N = 25;

int n, m, have[N];
map<string, int> hash;
string name[N];

int main() {
	int cas = 0;
	while (~scanf("%d%d", &n, &m) && n || m) {
		hash.clear();
		memset(have, 0, sizeof(have));
		for (int i = 1; i <= n; i++) {
			cin >> name[i];
			hash[name[i]] = i;
		}
		string a, b; int val;
		while (m--) {
			cin >> a >> b >> val;
			int u = hash[a], v = hash[b];
			have[u] += val;
			have[v] -= val;
		}
		printf("Case #%d\n", ++cas);
		for (int i = 1; i < n; i++) {
			if (have[i] < 0)
				cout << name[i] << " " << name[n] << " " << -have[i] << endl;
			else if (have[i] > 0)
				cout << name[n] << " " << name[i] << " " << have[i] << endl;
			have[n] -= have[i];
		}
		printf("\n");
	}
	return 0;
}