fork(10) download 
  1. #include<iostream>
  2. #include <list>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #define minimum(a,b) a<b?a:b
  6. #define MAX 123456789
  7.  
  8. using namespace std;
  9.  
  10. int *val,disjoint=0;
  11. long long int mi,ans=0,min_all;
  12.  
  13.  
  14. int read()
  15. {
  16.     int t=0;char c;
  17.     c=getchar();
  18.     while((c<'0'||c>'9'))c=getchar();
  19.     while(c>='0'&&c<='9')
  20.     {
  21.         t=(t<<3)+(t<<1)+c-'0';
  22.         c=getchar();
  23.     }
  24.     return t;
  25. }
  26.  
  27. class Graph
  28. {
  29.     int V;
  30.     list<int> *adj;
  31.     void DFSUtil(int v, bool visited[]);
  32. public:
  33.     Graph(int V);
  34.     void addEdge(int v, int w);
  35.     void DFS();
  36. };
  37.  
  38. Graph::Graph(int V)
  39. {
  40.     this->V = V;
  41.     adj = new list<int>[V];
  42.     val=(int *)malloc(sizeof(int)*(V));
  43. }
  44.  
  45. void Graph::addEdge(int v, int w)
  46. {
  47.     adj[v].push_back(w);
  48.     adj[w].push_back(v);
  49. }
  50.  
  51. void Graph::DFSUtil(int v, bool visited[])
  52. {
  53.     visited[v] = true;
  54.  
  55.     if(val[v]>=0)
  56.     {
  57.         //printf("{ %lld %d",mi,min_all);
  58.         mi=minimum(val[v],mi);
  59.         min_all=minimum(val[v],min_all);
  60.         //printf("%lld %d }\n",mi,min_all);
  61.     }
  62.  
  63.  
  64.     list<int>::iterator i;
  65.     for(i = adj[v].begin(); i != adj[v].end(); ++i)
  66.         if(!visited[*i])
  67.             DFSUtil(*i, visited);
  68. }
  69.  
  70. void Graph::DFS()
  71. {
  72.     bool *visited = new bool[V];
  73.     for(int i = 0; i < V; i++)
  74.         visited[i] = false;
  75.  
  76.     for(int i=1;i<V;i++)
  77.     {
  78.         if(visited[i]==false)
  79.         {
  80.             mi=MAX;
  81.             //printf("$%lld\n",mi);
  82.  
  83.             disjoint++;
  84.  
  85.             DFSUtil(i, visited);
  86.  
  87.             if(mi==MAX)
  88.             {
  89.  
  90.                 ans=-1;
  91.                 //printf("**\n");
  92.                 break;
  93.             }
  94.             else
  95.             ans+=mi;
  96.             //printf("%lld**\n",ans);
  97.         }
  98.         if(ans==-1)break;
  99.  
  100.     }
  101. }
  102.  
  103. int main()
  104. {
  105.     int n,m;
  106.     n=read();
  107.     m=read();
  108.  
  109.  
  110.  
  111.         Graph g(n+1);
  112.         min_all=MAX;	
  113.         for(int i=0;i<m;i++)
  114.         {
  115.             int a,b;
  116.             a=read();
  117.             b=read();
  118.             g.addEdge(a,b);
  119.         }
  120.         for(int i=1;i<=n;i++)
  121.             scanf("%d",&val[i]);
  122.  
  123.     if(n==1)
  124.     {
  125.         printf("0\n");
  126.     }
  127.     else
  128.     {
  129.         g.DFS();
  130.         if(disjoint==1)
  131.         {
  132.             printf("0\n");
  133.         }
  134.         else
  135.         {
  136.             if(ans==-1)
  137.                 printf("-1\n");
  138.             else
  139.             {
  140.                 disjoint-=2;
  141.                 ans+=disjoint*min_all;
  142.                 printf("%lld\n",ans);
  143.             }
  144.         }
  145.     }
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0s 3032KB
comments (?)
stdin 
3 1
2 3
1
-1
-1
stdout 
-1
https://ideone.com/L5Cenu
language:
C++ (gcc 8.3)
created:
12 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!