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++; } }