2257 Balancing Bank Accounts

http://poj.org/problem?id=2257

ほうしん

結局各個人の払うor払ってもらう金額のつじつまさえ合えばいいので、
各個人についていくら払うor払ってもらうかを計算してから
支払いができるところから順に払っていってやればよい。

ソース

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

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

const int inf = 1<<29;
int tranc[21][21],n;
int ac[21];

int main() {
  int tr,i,j,k,scenum = 1;
  while(cin>>n>>tr, n|tr) {
    cout<<"Case #"<<scenum<<endl;
    memset(tranc, 0, sizeof(tranc));
    memset(ac, 0, sizeof(ac));
    map<string,int> idx;
    map<int,string> ridx;
    string s,t;
    rep(i,n) {
      cin>>s;
      idx[s] = i;
      ridx[i] = s;
    }

    rep(i,tr) {
      cin>>s>>t>>j;
      ac[idx[s]] -= j;
      ac[idx[t]] += j;
    }

    while(true) {
      int s,t;
      rep(s,n) if(ac[s] > 0) break;
      rep(t,n) if(ac[t] < 0) break;
      if(s == n && t == n) break;
      int trans = min(ac[s], -ac[t]);
      cout<<ridx[s]<<" "<<ridx[t]<<" "<<trans<<endl;
      ac[s] -= trans;
      ac[t] += trans;
    }

    cout<<endl;
    scenum++;
  }
}