uva: 10048 – Audiophobia ( Floyd-Warshall minimax )

10048 – Audiophobia (Floyd-Warshall minimax)

 

Problem analysis:

  •  Consider a city map where the edges refer to streets and the nodes refer to crossings. The integer on each edge is the average intensity level of sound (in decibels) in the corresponding street
  • In this problem, given a city map you are required to determine the minimum sound intensity level you must be able to tolerate in order to get from a given crossing to another

Solution analysis:

  • It is not solvable using classic Floyd-Warshall algorithm, needs to modify as per problem requirements
  • MiniMax, MaxiMin problems can be solved using modified Floyd-Warshall

[stackoverflow]  To understand maximin paths (often called bottleneck paths) in a graph, consider the following problem. You have a road map of a country as a graph where each node represents an intersection and each edge represents a road. Each road has a weight limit, and if you drive a truck that exceeds the limit over that road it will break. You have a truck that you want to drive from some start location to some end location, and you want to put the maximum possible amount of weight on it. Given this, what path should you drive the truck in order to send the maximum possible weight?

If you think about this problem, for any path that you take in the graph, the maximum weight you can send along that path is going to be determined by the edge on that path with the minimum capacity. As a result, you want to find the path from the start to the destination whose minimum-capacity edge is maximized. The path with this property is called the maximin path or bottleneck path, and can be found with a straightforward set of modifications to mot shortest-path algorithms.

The minimax path represents the opposite idea – the path between two points that minimizes the maximum edge capacity.

 

Java solution:

 


import java.util.Scanner;

class Main_Audiophobia_10048_FW_Minimax {
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int testCase=0;
        while(true)
        {
            testCase++;            

            int cross=sc.nextInt(),street=sc.nextInt(),query=sc.nextInt();

            if(cross==0 && street==0 && query==0) break;

            int weight[][] = new int[cross+1][cross+1];
            int r,c;

            for(int i=1;i<=cross;i++)
                for(int j=1;j<=cross;j++)
                    weight[i][j] =  Integer.MAX_VALUE;

            for(int i=1;i<=street;i++)        
            {
                r = sc.nextInt();
                c = sc.nextInt();              
                weight[r][c] = weight[c][r] = sc.nextInt();
            }

            //floy-warshall minimax
            for(int k=1; k<=cross; k++)
                for(int i=1; i<=cross; i++)
                    for(int j=1;j<=cross;j++)
                        weight[i][j] = weight[j][i]  = Math.min(weight[i][j], Math.max(weight[i][k], weight[k][j]));

            if(testCase>1) System.out.println("");

            System.out.printf("Case #%d%n",testCase);

            for(int i=1;i<=query;i++)
            {
                r = sc.nextInt();
                c = sc.nextInt();

                if(weight[r][c] == Integer.MAX_VALUE) System.out.println("no path");
                else System.out.printf("%d%n", weight[r][c]);    

            }            
        }        
    }
}

Sample Input

7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4
0 0 0

Sample Output

Case #1
80
60
60

Case #2
40
no path
80

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)

2 Responses to uva: 10048 – Audiophobia ( Floyd-Warshall minimax )

  1. Pingback: uva: 544 – Heavy Cargo ( Floyd Warshall MaxiMin ) | M Moniruzzaman's Blog

  2. I think the admin of this site is in fact working hard for his site,
    since here every information is quality based data.

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: