Algorithm-Engineering Homework 6 Solution

With the fall of the Goat and the Serpent, Agent Ω hoped that she had finally taken down C.H.I.M.E.R.A., but she soon discovered that the organization had one more head: the Lion, a Martian military commander who had control over the vast automated defenses throughout the solar system.

These defenses included swarms of high-tech wardrones (which the Lion referred to his his "prides") that Agent Ω needed to eliminate before she could go after the Lion directly.  Agent Ω found a glitch in the Wardrones that would allow her to take over a single drone without being detected.  From that drone she can track enegy pulses from nearby drones; she can use this to decode their communication if she can see both drones involved.  But which drone should she take over to scan the most pairs of others?

To decide, she built a graph of which drones would be capable of monitoring each other. Each vertex represents a wardrone, and each edge indicates two that are close enough to track the energy pulses from the other.

You must determine which drone to take over such that Agent Ω can monitor the MOST pairs of drones as they communicate.

Input Format

The first line contains N, the number of wardrones being analyzed, and M, the number of pairs (edges) that could potentially scan each other's energy signatures.
The next M lines each have two values identifying all pairs of wardrones that could scan each other.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ drone IDs < N
Output Format

Output the count of how many PAIRS of wardrones could both be scanned if the optimal wardrone was taken over.  You should count the wardrone targeted AND all of its neighbors in the graph.

Example 0
Sample Input

5 7
0 1
0 2
0 3
1 2
1 3
1 4
2 3
Sample Output

 10
Explanation

If wardrone 1 is taken over, it will be able to monitor the energy signatures of 0, 2, 3, and 4.

This means that there are 10 pairs that it can monitor the communication of.  Drone 1 can scan four others that it directly communicates with PLUS it can monitor communications between (0,2), (0,3), (0,4), (2,3), (2,4), and (3,4).





Question 2




Agent Ω's initial attempt to take over the Lion's pride of wardrones ended up failing, but she did learn enough to figure out how to hack into a second, neighboring drone.  Now she's going to try again, this time with TWO drones monitoring their neighbors and working together.

You must determine which TWO adjacent drones will allow monitoring of the most pairs of drones as they communicate.

Input Format

The first line contains N, the number of wardrones being analyzed, and M, the number of pairs (edges) that could potentially scan each other's energy signatures.
The next M lines each have two values identifying all pairs of wardrones that could scan each other.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ drone IDs < N
Output Format

Output the count of how many PAIRS of wardrones could both be scanned if the optimal pair of wardrones were both taken over.  You should count the wardrones targeted AND all of its neighbors in the graph.

Example 0
Sample Input

7 8
0 1
0 3
0 4
0 6
2 3
2 4
2 5
3 4
Sample Output

 15
Explanation

If wardrones 0 and 3 are infiltrated, they can monitor communications of 6 of the 7 drones (including the two compromised).  With six drones, there are (6 x 5)/2 = 15 pairs that can be monitored.



Question 3





This time Agent Ω was able to compromise several drone swarms and monitor the messages the Lion was sending to them.  She could tell that he was having the swarms coordinate multiple attacks.  But how many?

Given a graph of which swarms are coordinating (vertices are swarms and edges indicate a pair of swarms are working together), can you figure out how many distinct missions the swarms are going on?  If there is a coordination path between any two swarms that means they are on the same mission.  If there is no path between them, they are on different missions.

Input Format

The first line contains N, the number of swarms being sent orders, and M, the number of pairs of swarms that are coordinating.
The next M lines each have two values identifying a pair of coordinating swarms.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ swarm IDs < N
Output Format

Print the number of indepent missions in the input graph.

Example 0
Sample Input

9 10
0 3
0 4
0 5
1 2
1 6
1 8
2 8
3 7
4 7
6 8
Sample Output

 2


Question 4 



Agent Ω tracked a set of swarms to Demos, one of Mars' moons, where they bombarded the surface.  Upon more investigation, she discovered that they had collapsed one of C.H.I.M.E.R.A.'s underground warehouse complexes with a single entrence.  Clearly there must be information there that the Lion does not want people to know about.

Given a graph of the warehouse complex where vertices represent storage rooms and edges indicate the tunnels connecting those storage rooms (along with a value representing the effort needed to clear that tunnel), determine the LEAST total effort that can be used to clear a subset of the tunnels such that all of the storage rooms will again be connected.

Input Format

The first line contains N, the number of storage rooms, and M, the number of hallways.
The next M lines each have three integer values. The first two identify the storage rooms involved, while the third provides the effort to clear the tunnel.
All graphs are gauranteed to be connected.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ efforst costs ≤ 1,000,000
0 ≤ storage room IDs < N
Output Format

A single value indicating the minimum total effort to clear enough tunnels to connect the storage rooms.

Example 0
Sample Input

5 6
0 1 5
0 2 10
0 3 2
1 3 3
1 4 8
3 4 1
Sample Output

 16





Question 5



Agent Ω - found valuable intel on C.H.I.M.E.R.A. in the underground warehouse.  But she also discovered that the other swarms destroyed more warehouses in other locations.

The first warehouse was tough to clear.  There was radiation (which could be avoided with a Giger counter) and damaged life support (so space suits were required) making the overall effort much higher than she expected.  As such, Agent Ω decided to be more careful when clearing out the other warehouses.  Rather than needing to find a path to EVERY storage room, she decided to pick a smaller number of KEY storage rooms to get to.  Additionally, the tunnels all turned out to be easy to clear - it was the storage rooms themselves that were the harder part.

Can you determine the FEWEST total storage rooms that Agent Ω will need to clear in order to have all of the key storage rooms connected?  You may assume the single entrence leads into one of the key storage rooms, so you don't need to consider it separately.

Hint: you will need to use a branch-and-bound approach to solving this problem.

NOTE 1: This problem is worth 400 points.  Any points beyond that are extra credit.  That said, the test cases get substantially more difficult as you go into the extra credit range.

The description provided for this problem:

NOTE 2: Your program must always either output the correct answer or timeout while searching. If your program every outputs an actively incorrect response for any test case, it will receive 0 credit on this problem (regardless of how many test cases it passes). Test cases on which you time out will not provide points, but will also not zero out points earned on other test cases.

Input Format

The first line contains three values: the number of storage rooms (N), the number of tunnels (M), and how many of those storage rooms are key [K]
The next M lines each describe a tunnel, indicating the unique id of each storage room it connects.
The final K lines each provide a single key vertex.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
1 ≤ K ≤ N
0 ≤ Storage Room IDs < N
Output Format

A single number indicating the minimum number of storage rooms that need to be cleared for all of the key storage rooms to be cleared as well as any others needed to make sure that they are all connected.

Example 0
Sample Input

5 6 2
0 1
0 2
0 4
1 4
2 3
2 4
0
3
Sample Output

 3
Explanation

If room 0, 2, and 3 are all cleared then both keys (0 and 3) will be clear as will a room that will connect them (2).