Блог пользователя t0nyukuk

Автор t0nyukuk, 12 лет назад, По-английски
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

It looks like a usual dp on a tree. I think you should write a comparator, like 'What vertex we should go into?'. Then run DFS, and at each step sort all children of the current vertex by this comparator and visit them in this exact order. Once you visit a subtree, it becomes a vertex with its own parameters.

I may be wrong, but it's the first solution I would think of.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    i will write comparator but which priority? i have no idea

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      Write the mathematical expression, what number of citizen will be dead if we go to the first city and then to the second. Then write the same expression if you visit the cities in the opposite order. Sign of the difference of these values will show which city of these two should be visited first.

»
12 лет назад, # |
Rev. 7   Проголосовать: нравится +2 Проголосовать: не нравится

my code is here and i dont know is it true solution

define fi first

define se second

define SIZE(A) ((int)A.size())

define pb push_back

using namespace std;

const int MAXN = 100010;

typedef pair<int,int> ii;

vector way[MAXN];

int n;

long long vic[MAXN];

struct node{

long long a,b,w,len;

node(int _a=0,int _b=0,int _w=0,int _len=0){

    a=_a;b=_b;w=_w;len=_len;

}

friend bool operator < (const node &a,const node &b){

    return a.b*b.a<b.b*a.a;

}

}ar[MAXN];

typedef set::iterator sit;

set G[MAXN];

bool used[MAXN];

node rec(int k,int t){

used[k]=true;
ar[k].w=k;
ar[k].len=t;
ar[k].b=t*2;
ar[k].a=vic[k];
node tmp;
for(int i=0;i<SIZE(way[k]);i++)
    if(!used[way[k][i].fi]){
       tmp=rec(way[k][i].fi,way[k][i].se);
       G[k].insert(tmp);
       ar[k].b+=tmp.b;
       ar[k].a+=tmp.a;
    }
return ar[k];

}

long long f(int k){

used[k]=true;
long long res=0;
long long time=0;

for(sit it=G[k].begin();it!=G[k].end();it++)
    if(!used[it->w]){

       res+=time*it->a+f(it->w)+it->len*it->a;

       time+=it->b;

    }

return res;

}

int main(){

scanf(" %d",&n);

for(int i=1;i<=n;i++)
    scanf(" %lld",&vic[i]);

for(int i=1,a,b,c;i<n;i++)
{
    scanf("%d %d %d",&a,&b,&c);
    way[a].pb(ii(b,c));
    way[b].pb(ii(a,c));
}
rec(1,0);
memset(used,0,sizeof used);

cout << f(1) << endl;

return 0;

}

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

AppleZ the previous comment for my wrong idea. Thanks