Sabamak's blog

By Sabamak, history, 3 weeks ago, In English,

First you must notice that in tags are written dfs and similar. Lets read the text There is one man who sell rumors.Rumors spread quickly by some people and your ambition is to find the minimal loss so that everybody here about them. In input The first line contains two integer numbers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — the number of characters in Overcity and the number of pairs of friends.

The second line contains n integer numbers ci — the amount of gold i-th character asks to start spreading the rumor.

Then m lines follow, each containing a pair of numbers (x[i], y[i]) which represent that characters x[i] and y[i] are friends (1 ≤ x[i], y[i] ≤ n, x[i] ≠ y[i]). It is guaranteed that each pair is listed at most once.

Lets explain first input 5 2 2 5 3 4 8 1 4 4 5 The first person tell 4-th and 4-th tell 5-th. The prices of first,4-th and 5-th persons are 2,4 and 8; So the minimal price is 2.If man tell first person he get 2. Because second and 3-th person tell no man get 5 and 3. So answer is 10.

How to solve this? lets take a sequence d also take vector v. In every v[i] push_back the input 1 4 4 5 e.g v[1].push_back(4) and because its two way graph you must push_back 1 in v[4]. Then lets write bfs. You must notice that variable of minimum must be maximum. if you don't know bfs look for my code :) Ok lets see my code

//#include<bits/stdc++.h> //using namespace std;

//long long a,b,c,d[900000],j,minemax,z,k,ans; //vectorv[900000]; //queueq; //bool o[9000000]; //int main(){ // ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); // cin>>a>>b; // for(int i = 1; i <= a; i++){ // cin>>d[i]; // } // for(int i = 1; i <= b; i++){ // cin>>z>>k; // v[z].push_back(k);v[k].push_back(z); // } // j=0; // while(j!=a){ // j++; // minemax=d[j]; // if(o[j]==false){ // o[j]=true; // q.push(j); // while(q.size()!=0){ // minemax=min(minemax,d[q.front()]); // for(int i = 0; i < v[q.front()].size(); i++){ // if(o[v[q.front()][i]]==false){ // o[v[q.front()][i]]=true; // q.push(v[q.front()][i]); // minemax=min(d[q.front()],minemax); // } // } // q.pop(); // } // ans+=minemax; // } // } // cout<<ans; If you understand try solve yourself If you like this Don't forget upvote :)

 
 
 
 
  • Vote: I like it
  • +24
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Awesome, thanks for sharing

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Is he your friend?

    Looking at both of your profile pictures, it seems both of you belong to the same pond.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks all of one who upvotes. if someone wants some problem to explain write in comments.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nice!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice explanation! I also had this question when I first saw that problem, glad people are now helping beginners so they can see this amazing resource when they need help.