Airports

Problem Statement

An airline company offers flights out of n airports, labeled from 1 to n.

The flight time tij from airport i to airport j is known for each ij, although it may not be the case that tij = tji.

Upon landing at a given airport, a plane must be inspected before flying again. Inspection time pi is dependent on the airport where the flight landed, not where previous flight originated.

Given a set of m flights that the airline company must provide, determine minimum number of planes company needs to purchase.

The airline may add unscheduled flights to move the airplanes around if that would reduce total number of planes needed.

Input File

Lines:

Line 1: n (number of airports) m (number of flights to maintain)

Line 2: (inspection times, pi, i = 1..n)

Line 3: j=1 (3-2), all the tij's (tii=0)

...

n+2 : j = n (n+2 - 2), all of the tij's

n+3: <source airport> <destination airport> <flight time>

...

n + 2 + m: ditto

Solution Notes

Airports problem:

• Set of n airports, trying to provide m flights between the planes
• We are provided with when the planes need to fly out of which airports at specified times

Input file detials: see above

START WITH THE FLIGHTS

Draw a connection from node A to node B if the starting/ending times of these two flights is reconcilable

Remember: this is a DAG

Now, we can convert this into two DAGs, and find the maximum bipartite matching in this graph.

The answer we are after is m - |max bipartite matching|

What do we mean when we say "maximum matching"?

We want maximum number of edges that connect two flights (u,v) (In other words, we want to maximize flight utility by matching up as many flights end-to-end as possible.)

Maximum matching means we've "matched up" the most connections possible, and therefore maximized the utility of each flight.

Any given matching that connects a node (flight) u in graph 1 to another node (flight) v in graph 2 is an edge representing a flight plan u to v. (Note that because flight times are not symmetric, graph 1 u to graph 2 v does not imply graph 1 v to graph 2 u. Although it may imply graph 2 u to graph 1 v. That is, u->v does not imply v->u

We want to minimize the number of unmatched edges.

Equivalent to minimizing flights arriving in a city and being stuck

Equivalent to maximizing size of matching.

Question:

• Looking for paths that connect all nodes trips that visit all nodes while minimizing......... ?

<flight source node> <flight destination node> <flight time>

Data structure

Start with the data structure:

• Constant number of flights m
• m are nodes, n are airports
• Draw graph: vertices are FLIGHTS
• Node i = flight i, node j = flight j
• Edge ij = whether it is possible to fly (service from flight i -> flight j)
• This graph should form a DAG
• We want the minimum number of paths needed to coer all vertices
• We want to find the minimum number of paths

Algorithm:

• Build a bipartite graph
• All flights
• copy of all flights
• u1 -> v2 indicates a plane can service flight u2 and then service flight v2.
• this is because we are not interested in "does this flight connect city A to city B" - rather, we're given a set of flights we have to make.
• We need the flights to cover those paths, the only question is how we'll do it.

Then we find a minimum path through all the nodes.