Code:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
int A[MAXN], B[MAXN];
vector<int> g[MAXN];
bool second_high_to_low(pair<int, int> a, pair<int, int> b){
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
}
pair<int, int> f(int u, int dad = -1){
vector< pair<int, int> > p;
for (int i = 0; i < g[u].size(); ++i){
int v = g[u][i];
if (v == dad) continue;
p.push_back( f(v, u) );
}
sort(p.begin(), p.end(), second_high_to_low);
int total = A[u];
int inhand = A[u] - B[u];
for (int i = 0; i < p.size(); ++i){
if (inhand > p[i].first){
inhand -= p[i].first - p[i].second;
}else{
total += p[i].first - inhand;
inhand = p[i].second;
}
}
return make_pair(total, inhand);
}
int main(){
int n, Case = 1;
while (cin >> n){
if (n == 0) break;
cout << "Case " << Case++ << ": ";
for (int i = 0; i < n; ++i){
int x, y, z;
cin >> x >> y >> z;
A[i] = x;
B[i] = y + z;
A[i] = max(A[i], B[i]);
g[i].clear();
}
for (int i = 0; i < n - 1; ++i){
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 3000;
for (int i = 0; i < n; ++i){
pair<int, int> p = f(i);
ans = min(ans, p.first);
}
cout << ans << endl;
}
return 0;
}
I want to konw how:
Code:
pair<int, int> p = f(i);
is transfered to
Code:
pair<int, int> f(int u, int dad = -1){
it is really confusing......
Code:
how f(i) becomes f(int u,int dad=-1)?
also g was declared as
Code:
vector<int> g[MAX];
how come it becomes g[u][i];?
Please help