uva: 11631 Dark Roads ( MST – Prim)

11631 Dark Roads

Problem analysis:

  • There will still be at least one illuminated path from every junction (vertex) in Byteland to every other junction(vertex)
  •  What is the maximum daily amount of money the government of Byteland can save, without making their inhabitants feel unsafe?
  • Connecting all the vertexes/nodes with minimum  lighting costs  and finding saving of operating roads lighting

Solution Hints:

  • This problem can be solved using Minimum Spanning Tree (MST) Prim’s, Kruskal’s  algorithms   –
  • Firstly, find the total costs of roads lighting
  • Secondly, find the minimum costs at least one illuminated path for connecting all junctions (vertexes)
  • Then, daily saving is deduction minimum costs from total costs.

Solution in Java and C++ are as follows:

 Solution in Java:


//TL
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class EdgeDR implements Comparable
{
    int u;
    int v;
    int w;    
    public EdgeDR(int u, int v, int w)
    {
        this.u = u;
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(EdgeDR other) {        
        return this.w - other.w;
    }
}

class VertexDR implements Comparable
{
    int id;
    int key;
    public VertexDR(int id, int key)
    {
        this.id = id;
        this.key = key;
    }

    @Override
    public int compareTo(VertexDR other) {
        return this.key - other.key;
    }
}

class Main_11631_DarkRoads_MST_Prims {

    public static void main(String[] args) {        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        
        final int INF = Integer.MAX_VALUE;
        int V,E, v1, v2,u, w;
        int totalCost, minCost;            
        int[] key;        
            
        ArrayList mstTree;
        ArrayList<arraylist<EdgeDR>> graph;
        PriorityQueue pq;

        while(true)
        {
            V = sc.nextInt();
            E = sc.nextInt();

            if(V==0) break;            

            totalCost = 0;        
            key= new int[V];
            pq =  new PriorityQueue(V);
            mstTree = new ArrayList(V);
            graph =  new ArrayList<ArrayList<EdgeDR>>(V);

            Arrays.fill(key, INF);

            for(int i=0; i
            {
                graph.add(new ArrayList<EdgeDR>());                    
            }

            for(int i=0;i<E;i++)
            {
                v1 = sc.nextInt();
                v2 = sc.nextInt();
                w = sc.nextInt();

                totalCost += w;
                graph.get(v1).add(new EdgeDR(v1,v2,w));
                graph.get(v2).add(new EdgeDR(v2,v1,w));                
            }    

            minCost = 0;
            key[0] = 0;            
            pq.add(new VertexDR(0,0));

            while(!pq.isEmpty())
            {        
                u = pq.poll().id;
                if(!mstTree.contains(u))
                {
                    minCost += key[u];
                    mstTree.add(u);
                }
                
                for(EdgeDR e:graph.get(u))
                {
                    if(!mstTree.contains(e.v) && e.w < key[e.v])
                    {
                        key[e.v] = e.w;                            
                        pq.add(new VertexDR(e.v, key[e.v]));
                    }
                }

            }

            System.out.println(totalCost - minCost);
        }

    }

}


Solution in C++:

c++ code here
Sample Input

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

Sample Output

51

 

 

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: