Sabamak's blog

By Sabamak, history, 5 years 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 :)

Full text and comments »

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