Tävlingsprogrammering/Uppgifter/Väktaren

Väktaren

Fysikstudenten Viktor extraknäcker somväktare på vaktbolaget VaktaSmart AB i grannstaden Vaktestad. Under en natt skall Viktor besöka P olika platser. Dessa förbinds av ett antal vägar (V stycken) som Viktor kan gå till fots. Viktor kan börja vaktpasset vid vilken plats som helst, och även sluta var han vill.

Viktor är väldigt begåvad och har uppfunnit en portabel materietransportör (s.k. teleporter), som han givetvis vill använda för att snabbare klara av sitt arbete så han kan åka hem och sova. Teleporten kan användas för att transportera Viktor från en plats till en annan, och under ett nattpass kan han använda den hur många gånger som helst. Transporten sker ögonblickligen och utan nämnvärd energiåtgång. På grund av begränsningar i konstruktionen måste dock Viktor ha varit på platsen han ska teleporteras till tidigare under samma vaktpass. Hjälp Viktor att planera sitt vaktpass genom att skriva ett program som beräknar hur snabbt han kan besöka alla platser, förutsatt att rutten är optimal. Indatat är konstruerat så att det är möjligt att besöka alla platser.

Indata

Första raden i filen vaktaren.dat innehåller två heltal, P (2 ≤ P ≤ 20,000) och V (P − 1 ≤ V ≤ 100,000). Därefter följer V rader som beskriver vägarna. De innehåller tre heltal vardera: ak, bk och tk (1 ≤ ak, bk ≤ P samt 0 ≤ tk ≤ 100), där ak och bk anger de två platser vägen går mellan, och tk den tid det tar att gå längs vägen.

Utdata

Programmet skall skriva ut den tid som den optimala vaktrundan tar.

Exempel

Svar

FIGUR 2. Kartan med platserna som ska besökas i exemplet. Viktor kan till exempel börja sitt pass på plats 5. Därifrån går han till platserna 3, 2 och 1 (tid 14). Sedan använder han teleportern för att förflytta sig tillbaka till plats 3. Sedan går han till plats 7, 6 och 4 (tid 7). Den totala gångtiden blir 21.

Lösning

Det här problemet är exakt Minimum Spanning Tree-problemet, och det efterfrågade är vikten (dvs. totala tiden). Här är en lösning som använder Kruskals algoritm, tillsammans med Disjunkta set-datastrukturen, med path compression. Programmet går på mindre än 0.1 sekund för värsta testfallet.

#include <cstdio>
#include <algorithm>

static int P, V;

static struct Vag {
	int from;
	int to;
	int len;
	bool operator<(const Vag& o) const {
		return len < o.len;
	}
} vagar[100000];

static int platser[20000];
static int get_root(int plats){
	if (platser[plats] == plats)
		return plats;
	return platser[plats] = get_root(platser[plats]);
}
static void merge(int plats1, int plats2){
	platser[get_root(plats1)] = get_root(plats2);
}
static bool same_set(int plats1, int plats2){
	return get_root(plats1) == get_root(plats2);
}

int main(){
	FILE* fp = fopen("data/vaktaren.dat", "r");
	fscanf(fp, "%d %d", &P, &V);
	
	for(int i=0; i<P; i++)
		platser[i] = i;
	
	for(int i=0; i<V; i++){
		fscanf(fp, "%d %d %d", &vagar[i].from, &vagar[i].to, &vagar[i].len);
		vagar[i].from--, vagar[i].to--;
	}
	
	std::sort(vagar, vagar+V);
	
	int total_tid = 0;
	for(int i=0; i<V; i++){
		Vag& v = vagar[i];
		if (!same_set(v.from, v.to)){
			merge(v.from, v.to);
			total_tid += v.len;
		}
	}
	
	printf("%d\n", total_tid);
}

Lösning i Java som tar 3-5 sek för de två värsta testfallen. Det som tar tid är inläsningen, vilken tar ca 3 sek, medan algoritmen går på mindre än 1 sek.

import java.util.*;
import java.io.*;

public class Vaktaren
{
	//Orka fånga exceptions. Vi är lata och säkra på vår sak.
	public static void main(String [] klein) throws FileNotFoundException
	{
		//Vi ska läsa av filen vaktaren.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\vaktaren.dat"));

		//Antalet platser.
		int P = scan.nextInt();

		//Lagrar platserna man ska besöka.
		Plats [] plats = new Plats [P+1];

		//Skapar platserna.
		for(int i = 1; i<=P; i++) plats[i] = new Plats();

		//Antalet vägar.
		int V = scan.nextInt();

		//Läser in vägarna och drar dem mellan platser.
		for(int i = 0; i<V; i++)
		{
			int from = scan.nextInt();
			int to = scan.nextInt();
			int cost = scan.nextInt();

			plats[from].ways.add(new Way(to, cost));
			plats[to].ways.add(new Way(from, cost));
		}

		//Vår heap (kö). Vid skapandet så slänger vi in vägarna från plats 1.
		PriorityQueue <Way> qu = new PriorityQueue <Way> (plats[1].ways);

		//Och då kan vi säga att vi har börjat vandringen i plats 1 och den
		//är därtill dessutom besökt nu.
		plats[1].visited = true;

		//Det har gått 0 tid.
		int tid = 0;

		//Vi kör på tills vi avverkat alla vägar.
		while(!qu.isEmpty())
		{
			//Plockar den kortaste vägen vi hittills känner till.
			Way w = qu.poll();

			//Platsen vägen leder till.
			Plats p = plats[w.to];

			//Om vi inte redan besökt platsen besöker vi den.
			if(!p.visited)
			{
				//Då är den besökt.
				p.visited = true;

				//Och det har gått lite tid.
				tid += w.cost;

				//Och vi känner till nya vägar.
				qu.addAll(p.ways);
			}
		}

		//Skriver ut svaret.
		System.out.println("Minimal tid: " + tid);
	}

	//En klass som beskriver en plats.
	private static class Plats
	{
		//Om platsen är besökt.
		boolean visited = false;

		//Vägarna som går från denna plats.
		Collection <Way> ways;

		public Plats()
		{
			ways = new LinkedList <Way> ();
		}
	}

	//En klass som beskriver en väg.
	private static class Way implements Comparable<Way>
	{
		//Hur lång tid det tar att gå längs vägen.
		int cost;

		//Vart (till vilken plats) vägen leder.
		int to;

		public Way(int to, int cost)
		{
			this.to = to;
			this.cost = cost;
		}

		//Metod som gör att vägar kan stoppas in i Heapar och Träd m.m.
		//Vägarna sorteras främst efter kostnad och då med lägst kostnad först.
		//Två vägar med samma kostnad sorteras efter destination
		public int compareTo(Way w)
		{
			if(cost<w.cost) return -1;
			else if(cost>w.cost) return 1;
			else
			{
				if(to<w.to) return -1;
				else if(to>w.to) return 1;
				else return 0;
			}
		}
	}
}