Edmonds-Karp辅导、c++/Python程序语言讲解、辅导Java、讲解network 讲解留学生Processing|辅导留学生
- 首页 >> 其他 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
43reported 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
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
43reported 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