fork(1) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<cstdio>
  4. #define max 10000000
  5. #define INF 100000000
  6. using namespace std;
  7.  
  8. vector<int> queue;
  9. vector<int> adj[max];
  10. vector<int> connected_comp (max,0);
  11. vector<int> tax;
  12. vector<int> min_tax;
  13.  
  14. int n,e,min_count=0,min_val;
  15.  
  16. void enqueue(int val) {
  17.      queue.push_back(val);
  18. }
  19. int dequeue(){
  20.      int first_ele=queue[0];
  21.      queue.erase(queue.begin());
  22.      return first_ele;
  23. }
  24.  
  25. void print_queue(){
  26.   int i;
  27.   for(i=0;i<queue.size();i++)
  28.     cout<<queue[i]<<",  ";     
  29.   cout<<endl;
  30. }
  31.  
  32. void createAdjecenyList(int u,int v){
  33.      adj[u].push_back(v);
  34.        adj[v].push_back(u);
  35. }
  36. void printAdjecenyList(){
  37.      int i,j;
  38.      for(i=1;i<=n;i++){
  39.          cout<<i;
  40.          for(j=0;j!=adj[i].size();j++){
  41.              cout<<" -> "<<adj[i][j];
  42.          }          
  43.          cout<<endl;       
  44.      }
  45. }
  46.  
  47. int find_starting_vertex(int start){
  48.     int i;
  49.     if(start >= n) return -1;
  50.     else {
  51.       for(i=start+1;i<=n;i++){
  52.          if(connected_comp[i]==0) 
  53.            return i;
  54.       }
  55.     }
  56.     return -1;
  57. }
  58.  
  59. void bfs(int v,int index){
  60.   int t,i,u,j,minimum;
  61.   enqueue(v);
  62.   connected_comp[v]=index;
  63.   if(tax[v]>0) minimum=tax[v];
  64.     else minimum=INF;
  65.   while(queue.size()>0){
  66.         t = dequeue();      
  67.         for(i=0;i!=adj[t].size();i++){
  68.            u=adj[t][i];
  69.            if(connected_comp[u]==0){
  70.                connected_comp[u]=index;
  71.                if(minimum>tax[u] && tax[u]>0) minimum=tax[u];
  72.                enqueue(u);
  73.            }              
  74.         }
  75.   }
  76.   if(minimum != INF && minimum != 0) 
  77.      min_tax.push_back(minimum);
  78.      if(min_val>minimum) min_val=minimum;
  79. }
  80.  
  81. int explore_conn_comp(){
  82.      int start =find_starting_vertex(0);
  83.      int index=1;
  84.      while(1 ) {
  85.           bfs(start,index);
  86.           start =find_starting_vertex(start);
  87.           if(start==-1) break;
  88.           index++;
  89.      }
  90.      return index;
  91. }
  92. int main(){
  93.     int u,v,i,number,c,sum,taxsize;
  94.     min_val=INF;
  95.     scanf("%d",&n);
  96.     scanf("%d",&e);
  97.     while(e--) {
  98.        scanf("%d %d",&u,&v);
  99.        createAdjecenyList(u,v);  
  100.     }
  101.     tax.push_back(0);
  102.     for(i=1;i<=n;i++) {
  103.        scanf("%d",&c);
  104.        tax.push_back(c);
  105.     }
  106.     number=explore_conn_comp();
  107.   //  for(i=0;i<min_tax.size();i++) printf("%d  ",min_tax[i]);
  108.  
  109. //    printf("\n%d\n",min_val);
  110.    taxsize=min_tax.size();
  111.     sum=0;
  112.     if(number==1) printf("0\n");
  113.     else if(number>taxsize) printf("-1\n");
  114.     else  {   for(i=0;i<min_tax.size();i++) sum=sum+min_tax[i]+min_val;
  115.          printf("%d\n",sum-2*min_val);
  116.     }
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0.17s 120256KB
comments (?)
stdin
copy 
6 4
1 2
2 3
3 4
3 4
4
5
2
6
9
10
stdout
copy 
23
https://ideone.com/OZwGxj
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!