fork download
copy 
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.Iterator;
  4.  
  5. class GALACTIK {
  6.     public static void main(String args[])throws IOException{
  7.         StringBuilder output=new StringBuilder();
  8.         Reader read=new Reader();
  9.         int N=read.nextInt();
  10.         int M=read.nextInt();
  11.         Graph obj=new Graph(N);
  12.  
  13.         for (int i = 0; i <M ; i++) {
  14.              obj.addEdge(read.nextInt(),read.nextInt());
  15.         }
  16.         for (int i = 0; i <N ; i++) {
  17.            int t=read.nextInt();
  18.            if(t>=0)
  19.                obj.tax[i+1]=t;
  20.            else
  21.                obj.tax[i+1]=Integer.MAX_VALUE;
  22.         }
  23.         obj.DFS();
  24.     }
  25.     static class Graph {
  26.         int V;
  27.         ArrayList<Integer> adj[];
  28.         int tax[];
  29.         Graph(int vertices){
  30.             V=vertices+1;
  31.             tax=new int[V];
  32.             adj=new ArrayList[V];
  33.             for (int i = 0; i <V ; i++) {
  34.                 adj[i]=new ArrayList<>();
  35.             }
  36.         }
  37.         void addEdge(int from,int to){
  38.             adj[from].add(to);
  39.             adj[to].add(from);
  40.         }
  41.         void DFS(){
  42.             boolean visited[]=new boolean[V];
  43.             int size=0;
  44.             int min=Integer.MAX_VALUE;
  45.             boolean reach=true;
  46.             long sum=0;
  47.             for (int i = 1; i <V ; i++) {
  48.                 if(!visited[i]){
  49.                     int curr=DFSUtil(i,-1,visited);
  50.                     if(curr==Integer.MAX_VALUE)
  51.                         reach=false;
  52.                     sum+=(long)curr;
  53.                     //finds global minimum
  54.                     min=Math.min(min,curr);
  55.                     //count the number of components
  56.                     size++;
  57.                 }
  58.             }
  59.  
  60.             //System.out.println(size);
  61.             if(size==1) //if there is only one component
  62.                 sum=0;
  63.             if(size>2 && !reach) //if number of components>2 and there is a component which is not reachable
  64.                 sum=-1;
  65.             if(size>2 && reach) //find cost required if all components are reachable
  66.                 sum=sum+(size-2)*min;
  67.             System.out.println(sum);
  68.         }
  69.  
  70.         //returns the local minimum of a component
  71.         int DFSUtil(int node,int parent,boolean visited[]){
  72.             visited[node]=true;
  73.             Iterator<Integer> itr=adj[node].iterator();
  74.             int min=tax[node];
  75.             while(itr.hasNext()){
  76.                 int v=itr.next();
  77.                 if(!visited[v]) {
  78.                     min = Math.min(min, DFSUtil(v, node, visited));
  79.                 }
  80.             }
  81.             return min;
  82.         }
  83.     }
  84.     static class Reader
  85.     {
  86.         final private int BUFFER_SIZE = 1 << 16;
  87.         private DataInputStream din;
  88.         private byte[] buffer;
  89.         private int bufferPointer, bytesRead;
  90.  
  91.         public Reader()
  92.         {
  93.             din = new DataInputStream(System.in);
  94.             buffer = new byte[BUFFER_SIZE];
  95.             bufferPointer = bytesRead = 0;
  96.         }
  97.  
  98.         public Reader(String file_name) throws IOException
  99.         {
  100.             din = new DataInputStream(new FileInputStream(file_name));
  101.             buffer = new byte[BUFFER_SIZE];
  102.             bufferPointer = bytesRead = 0;
  103.         }
  104.  
  105.         public String readLine() throws IOException
  106.         {
  107.             byte[] buf = new byte[64]; // line length
  108.             int cnt = 0, c;
  109.             while ((c = read()) != -1)
  110.             {
  111.                 if (c == '\n')
  112.                     break;
  113.                 buf[cnt++] = (byte) c;
  114.             }
  115.             return new String(buf, 0, cnt);
  116.         }
  117.  
  118.         public int nextInt() throws IOException
  119.         {
  120.             int ret = 0;
  121.             byte c = read();
  122.             while (c <= ' ')
  123.                 c = read();
  124.             boolean neg = (c == '-');
  125.             if (neg)
  126.                 c = read();
  127.             do
  128.             {
  129.                 ret = ret * 10 + c - '0';
  130.             }  while ((c = read()) >= '0' && c <= '9');
  131.  
  132.             if (neg)
  133.                 return -ret;
  134.             return ret;
  135.         }
  136.  
  137.         public long nextLong() throws IOException
  138.         {
  139.             long ret = 0;
  140.             byte c = read();
  141.             while (c <= ' ')
  142.                 c = read();
  143.             boolean neg = (c == '-');
  144.             if (neg)
  145.                 c = read();
  146.             do {
  147.                 ret = ret * 10 + c - '0';
  148.             }
  149.             while ((c = read()) >= '0' && c <= '9');
  150.             if (neg)
  151.                 return -ret;
  152.             return ret;
  153.         }
  154.  
  155.         public double nextDouble() throws IOException
  156.         {
  157.             double ret = 0, div = 1;
  158.             byte c = read();
  159.             while (c <= ' ')
  160.                 c = read();
  161.             boolean neg = (c == '-');
  162.             if (neg)
  163.                 c = read();
  164.  
  165.             do {
  166.                 ret = ret * 10 + c - '0';
  167.             }
  168.             while ((c = read()) >= '0' && c <= '9');
  169.  
  170.             if (c == '.')
  171.             {
  172.                 while ((c = read()) >= '0' && c <= '9')
  173.                 {
  174.                     ret += (c - '0') / (div *= 10);
  175.                 }
  176.             }
  177.  
  178.             if (neg)
  179.                 return -ret;
  180.             return ret;
  181.         }
  182.  
  183.         private void fillBuffer() throws IOException
  184.         {
  185.             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  186.             if (bytesRead == -1)
  187.                 buffer[0] = -1;
  188.         }
  189.  
  190.         private byte read() throws IOException
  191.         {
  192.             if (bufferPointer == bytesRead)
  193.                 fillBuffer();
  194.             return buffer[bufferPointer++];
  195.         }
  196.  
  197.         public void close() throws IOException
  198.         {
  199.             if (din == null)
  200.                 return;
  201.             din.close();
  202.         }
  203.     }
  204. }
  205.  
  206. /*
  207. 8 7
  208. 1 2
  209. 2 3
  210. 1 3
  211. 4 5
  212. 5 6
  213. 4 6
  214. 7 8
  215. 1
  216. 3
  217. 5
  218. 2
  219. 4
  220. 6
  221. 7
  222. 5
  223.  
  224. 8 7
  225. 1 2
  226. 2 3
  227. 1 3
  228. 4 5
  229. 5 6
  230. 4 6
  231. 7 8
  232. 1
  233. 3
  234. 5
  235. 2
  236. 4
  237. 6
  238. -2
  239. -3
  240.  
  241. 3 3
  242. 1 2
  243. 2 3
  244. 3 1
  245. -1
  246. -2
  247. -3
  248.  
  249. 3 1
  250. 1 2
  251. 1
  252. 2
  253. 5
  254.  
  255. 7 4
  256. 1 2
  257. 2 3
  258. 1 3
  259. 5 6
  260. 3
  261. -1
  262. -1
  263. 2
  264. 6
  265. 8
  266. 4
  267. */
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
6 6
1 2
2 3
1 3
4 5
5 6
4 6
1
3
5
2
4
6
stdout
copy 
3
https://ideone.com/Wl3WYn
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

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!