Tävlingsprogrammering/Uppgifter/Flygbolaget igen

Flygbolaget igen

Bo Arding (se uppgiften Flygbolaget) har nu funderat lite till och insett att om man utökar antalet flighter kan man kanske klara sig undan med färre flygplan. Skriv ett program som beräknar hur många plan man behöver för att uppfylla samtliga flighter (ursprungliga och nya) om man får skapa godtyckligt många nya flighter mellan flygplatserna. Indata följer samma specifikationer och gränser som för Flygbolaget. De nya flighterna får flygtider enligt "avståndstabellen".

Exempel: Indata

6 7
0 150 50 110 45 120
145 0 180 90 60 80
50 160 0 40 38 45
110 90 37 0 50 20
47 60 40 52 0 65
120 80 40 20 60 0
1 2 170
6 5 400
5 4 470
2 6 318
4 3 520
3 6 700
2 1 25

Exempel: Utdata

2

Exempel: Förklaring

Bo kan exempelvis lägga ut en ny flight från flygplats 2 till flygplats 4 med avgångstid när som helst mellan 320 och 430. Då behöver han endast två flygplan medan det krävdes tre med de ursprungliga flighterna (se Flygbolaget).

Lösning

Precis som i den enklare uppgiften Flygbolaget gäller det att para ihop så många ankommande flighter som möjligt med avgående flighter som kan använda samma flygplan. Den enda skillnaden är att vi nu inte är begränsade till flighter som avgår från samma flygplats som planet kom in till, eftersom vi i denna uppgift kan skapa så många extraflighter vi vill. När vi räknar ut huruvida det går att koppla ihop två flighter är vi hjälpta av att avståndstabellen uppfyller triangelolikheten. Därmed vet vi nämligen att det aldrig kan vara värt att göra mer än en extraflight för att få ihop en koppling: det tar alltid minst lika lång tid om man mellanlandar. Annars hade vi fått börja med att räkna ut kortaste vägen mellan varje par av flygplatser med exempelvis Floyd-Warshall's algoritm.

När vi räknat ut alla möjliga kopplingar (vilket kan representeras som en s.k. bipartit graf med ankomster i en kolumn och avgångar i en annan kolumn och bågar mellan möjliga kopplingar) uppstår ett matchningsproblem, eftersom vi bara får koppla ihop varje ankomst med högst en avgång (det finns ju bara ett flygplan). Eftersom antalet flighter kan vara upp till 500 så krävs det en effektiv algoritm för att få full poäng på uppgiften. Matchningsproblemet är ett klassiskt grafproblem men att lösa det effektivt är inte ett problem som vi brukar ha på PO, faktum är att det inte ens förekommer på IOI, detta för att inte ge för mycket fördel till "algoritmnördar" (däremot förekommer det ibland på BOI och andra regionala tävlingar). Med tanke på kopplingen till uppgift 3 så kunde vi dock inte låta bli, och i onlinekvalet hade man ju chans att leta upp hur man gör, t.ex. på vår egen tränings-sajt. Och framför allt är det en sådan vacker algoritm att den förtjänar lite utrymme.

Det man gör är att starta från exempelvis en tom matchning och sedan öka antalet kopplingar successivt. I varje omgång letar man efter en väg (augmenting path) som har följande egenskaper:

• Den börjar i en omatchad ankomst-nod och slutar i en omatchad avgångsnod.
• Den följer (givetvis) bågarna i grafen.
• När den går "framåt" (från ankomst till avgång) följer den en båge som inte ingår i matchningen
• När den går "bakåt" (från avgång till ankomst) följer den en båge som ingår i matchningen.

En sådan väg kan t.ex. hittas med vanlig djupet-först-sökning, där vi sparar var vi varit så vi inte besöker samma nod mer än en gång. Det enklaste exemplet på en sådan väg är en ensam båge som inte ingår i någon matchning, den kan vi lägga till direkt. Nästa typ är en Z-formad väg ABCD med tre bågar varar den mittersta (BC) ingår i den nuvarande matchningen. Då kan vi skifta så att istället AB och CD ingår i matchningen (men inte BC). Mer generellt, när vi hittat en augmenting path så skiftar vi de matchade och omatchade bågarna så att storleken på matchningen växer med 1. Det roliga med denna algoritm är att den verkligen ger det rätta svaret: när det inte längre finns någon augmenting path så är matchningen maximal.

Lösning i C:

#include <stdio.h>
#define MAXN 1000
#define MAXF 1000

int ed[MAXF][MAXF],taken[MAXF],prev[MAXF],next[MAXF],n;

int MLX(int now) {   //Vi befinner oss på ankomstnoden now och ska hitta en augmenting path
  int p;
  if(now==-1) return 1;   //Detta betyder att vi har försökt gå till en omatchad avgångsnod, alltså är vi färdiga.
  if(taken[now]) return 0;   //Här har vi redan varit och det gick inget vidare
  taken[now]=1;
  for(p=0;p<n;p++) if(ed[now][p]) {     //Loopa över alla bågar från now
      if(MLX(prev[p])) {     //Rekursera. Om den returnerar 1 så har vi hittat en augmenting path så vi skiftar bågarna
        prev[p]=now;
        next[now]=p;
        return 1;
      }
    }
  return 0;
}
   
int main() {
  int N,i,j,nm,d[MAXN][MAXN], from[MAXF],to[MAXF],dep[MAXF];
  scanf("%d %d", &N,&n);
  for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d", &d[i][j]);
  for(i=0;i<n;i++) {
    scanf("%d %d %d", &from[i], &to[i], &dep[i]); from[i]--; to[i]--;
    next[i]=-1;
    prev[i]=-1;
  }
  for(i=0;i<n;i++) {
    for(j=0;j<n;j++) 
      ed[i][j]=(dep[i]+d[from[i]][to[i]]+d[to[i]][from[j]]<=dep[j]);   //Går det att koppla ihop flight i med flight j? (med eller utan extraflight)
      }
  nm=0;
  while(1) {
    for(i=0;i<n;i++) taken[i]=0;   
    for(i=0;i<n;i++) if(next[i]==-1 && MLX(i)) {      //Loopa över omatchade ankomstnoder och leta efter en augmenting path
      nm++;  //Öka storleken på matchningen
      break;
    }
    if(i==n) break;    //Ingen augmenting path hittad: matchningen är maximal
  }
  printf("%d\n", n-nm);
  return 0;
}