G[u].push back(v);
here G[5] is a vector
u,v are int
Printable View
G[u].push back(v);
here G[5] is a vector
u,v are int
I want to konw how: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;
}
is transfered toCode:pair<int, int> p = f(i);
it is really confusing......Code:pair<int, int> f(int u, int dad = -1){
also g was declared asCode:how f(i) becomes f(int u,int dad=-1)?
Please helpCode:vector<int> g[MAX];
how come it becomes g[u][i];?
It's a C++ feature called default arguments. Unless you provide a different argument for dad, it will be -1 in the function. What's the reason, you think? A default argument is a good way to add functionality or a fix to a function working in existing code without breaking existing code.
It's inherent in the type of g. An array of vectors can be indexed that way.Quote:
also g was declared asPlease helpCode:vector<int> g[MAX];
how come it becomes g[u][i];?
Please help yourself to the detailed reference on the web you were linked earlier.
You're an idiot. He asks about both vectors and default arguments in his post. All you have to do is read his code to notice this, but I will explain my answer.
f() is a function.
pair<int, int> is the return value, f is the function name, and there's the parameter list "(int u, int dad = -1)". dad = -1 in this context is a default argument. You can also see the function body.
I mean, if I read the question wrong, you're welcome to put some effort in and actually correct me.Quote:
Originally Posted by enakta13
But I also answer his other question.
Perhaps I didn't answer it well, but what could I do? It would be nice if he knew more words.Quote:
Originally Posted by enakta13