代做Edmonds-Karp、代写c/c++，Java，Python程序语言、代做algorithm

日期：2019-04-04 11:45

Problem 47. Compute the maximum flow of the following flow network using

the Edmonds-Karp algorithm, where the source is S and the sink is T. Show the

residual network after each flow augmentation. Write down the maximum flow

value.

Problem 48. A new and very aggressive species of ants is created in a bioinformatics

lab in Venice. The ants begin to spread throughout the city. They

cannot swim, so they can only pass a canal by going over a bridge. If they reach

the airport, they would spread to the entire world, most likely ending the human

race.

You can spray a special insecticide on a bridge to stop ants from going over

that bridge.

The map of Venice is given to you as a graph where edges represent bridges.

Two special nodes represent the lab and the airport.

Give an efficient algorithm to compute the minimum number of bridges that

have to be sprayed with insecticide to prevent the ants from reaching the airport.

Your algorithm should also output the list of bridges.

Problem 49. The Island of Sodor is home to a large number of towns and villages,

connected by an extensive rail network. Recently, several cases of a deadly

contagious disease (either swine flu or zombies; reports are unclear) have been

43

reported in the village of Ffarquhar. The controller of the Sodor railway plans to

close down certain railway stations to prevent the disease from spreading to Tidmouth,

his home town. No trains can pass through a closed station. To minimize

expense (and public notice), he wants to close down as few stations as possible.

However, he cannot close the Ffarquhar station, because that would expose him to

the disease, and he cannot close the Tidmouth station, because then he couldn’t

visit his favorite pub.

Describe and analyze an efficient algorithm to find the minimum number of

stations that must be closed to block all rail travel from Ffarquhar to Tidmouth.

The Sodor rail network is represented by an undirected graph, with a vertex for

each station and an edge for each rail connection between two stations.

Problem 50. (Difficulty 3) You are running an online ice cream store. You offer

m different flavors {1, 2, . . . , m}, and you have in stock si scoops of flavor i. You

receive requests from n different customers {1, 2, . . . , n}. Customer i is willing to

buy at most di,j scoops of flavor j, and at most hi scoops overall. Compute the

maximum number of scoops that you can sell.

Problem 51. (Difficulty 4) A school has S students, C classes, and T teams. Each

student belongs to exactly one class, but is a member of one or more teams. Each

team wants to select a member to be its representative in the student council. But

a student cannot represent more than one team. The school also does not want to

have more than 10 students in the council coming from the same class. Describe

an algorithm to determine if it is possible to form a student council subject to

these constraints.

44