BWInf 2011, Frage 5: Partnerstädte

8

Dies ist eine Herausforderung, die ursprünglich eine Aufgabe des Bundeswettbewerbs Informatik war , einem Wettbewerb für Schüler. Im Gegensatz zu der ursprünglichen Frage, bei der Sie eine gute Lösung finden und eine Dokumentation schreiben müssen, möchte ich, dass Sie dies Golf spielen. Ich versuche die Frage so gut wie möglich zu wiederholen:

Herausforderung

Viele Städte in Europa haben sogenannte Partnerstädte . In diesem Jahr gibt es ein besonderes Jubiläum, bei dem jedes Paar Partnerstädte in der EU ein Festival organisiert, um ihre Partnerschaft zu feiern. Um sicherzustellen, dass keine Stadt zu viele Festivals organisieren muss, gibt es in jeder Stadt eine Begrenzung der Festivals, die sie organisieren kann. Ist es möglich, die Feste so auf die Partnerstädte zu verteilen, dass jedes Paar Partnerstädte ein Festival in einer der beiden Städte organisiert und keine Stadt mehr Festivals organisiert, als es erlaubt ist? Wenn ja, erklären Sie wie.

Dies ist eine Karte einiger Städte, ihrer Partnerschaften und ihrer Grenzen für Festivals.

Partnerschaften http://dl.dropbox.com/u/1869832/partnerships.png

Bedarf

  • Ihr Programm muss das Problem für beide Testfälle jeweils in einer Minute beenden. (Siehe unten)
  • Informationen zum Eingabeformat finden Sie in den Testfällen.

  • Die Ausgabe sollte leer sein, wenn keine Lösung vorhanden ist, und sollte ansonsten das folgende Format haben: Eine Zeile für jedes Paar Partnerstädte, afalls city1das Festival organisiert wird, bandernfalls.

    <city1>, <city2>, <a/b>

  • Die Lösung mit der geringsten Anzahl von Zeichen, die die Anforderungen erfüllt, gewinnt. Bei einem Unentschieden gewinnt das zuerst eingereichte Programm.

  • Es gelten die üblichen Code-Golf-Regeln.

Testfälle

Die ursprüngliche Aufgabe hatte zwei Testfälle. Ich habe sie auf Github hochgeladen .

code-golf graph-theory FUZxxl
quelle
Hinweis: Es gibt eine einfache Reduzierung auf den ganzzahligen Max-Flow.
Peter Taylor
@ Peter was ist mit dem zweiteiligen Matching?
FUZxxl
Die Reduzierung ist eine geringfügige Erweiterung der standardmäßigen Reduzierung des zweiteiligen Abgleichs und sollte effizienter sein als eine Reduzierung über den zweiteiligen Abgleich (was erfordern würde, dass jede Stadt in nKnoten umgewandelt wird, wo ndie Budgetgrenze der Stadt liegt).
Peter Taylor

Antworten:

2

Python, 380 Zeichen

import sys
N={};H={};X={}
for L in open(sys.argv[1]):n,x,y=L.split('"');N[x]=int(n);H[x]=0;X[x]=[]
for L in open(sys.argv[2]):s,t=eval(L);X[s]+=[t]
p=1
while p:
 p=0
 for x in N:
  if len(X[x])>N[x]:
   p=1;S=[y for y in X[x]if H[y]<H[x]]
   if S:X[x].remove(S[0]);X[S[0]]+=[x]
   else:H[x]+=1
   if H[x]>2*len(N):sys.exit(0)
for x in N:
 for y in X[x]:print'"%s", "%s", a'%(x,y)

Dieser Code verwendet einen Maximum-Flow-Algorithmus im Push-Relabel- Stil. N[x]ist die Anzahl der Parteien, bei denen erlaubt ist x, X[x]ist die Liste der Partnerstädte, in denen derzeit gehostet werden soll x(die länger sein können als N[x]während des Algorithmus), und H[x]ist die beschriftete Höhe von x. Für jede überzeichnete Stadt schieben wir entweder eine ihrer geplanten Partys in eine niedrigere Partnerstadt oder erhöhen ihre Höhe.

Keith Randall
quelle
2

C #, 1016 992 916 Zeichen

Dauert 4 Sekunden für mich auf dem großen Test-Set; Leistung kann leicht eine Menge , indem sie verbessert werden Xeine HashSet<s>eher als ein List<s>.

using System;using System.Collections.Generic;using System.IO;using System.Linq;using
s=System.String;class D<T>:Dictionary<s,T>{}class E:D<int>{static void Main(s[]x){s
S="",T=">",l;s[]b;D<E>R=new D<E>(),P=new D<E>();R[S]=new E();R[T]=new E();foreach(s L in
File.ReadAllLines(x[0])){b=L.Split('"');s f=b[1];R[T][f]=0;R[f]=new E();P[f]=new
E();R[f][T]=int.Parse(b[0].Trim());}foreach(s L in File.ReadAllLines(x[1])){b=L.Split('"');s
f=b[1],t=b[3],v=f+t;R[v]=new
E();R[v][S]=R[f][v]=R[t][v]=0;P[f][t]=R[S][v]=R[v][f]=R[v][t]=1;}for(;;){List<s>X=new
s[]{S}.ToList(),A=X.ToList();w:while((l=A.Last())!=T){foreach(s t in
R[l].Keys){if(!X.Contains(t)&R[l][t]>0){X.Add(t);A.Add(t);goto
w;}}A.RemoveAt(A.Count-1);if(!A.Any())goto q;}l=S;foreach(s n in
A.Skip(1)){R[l][n]--;R[n][l]++;l=n;}}q:if(R[S].Values.Contains(1))return;foreach(s
f in P.Keys)foreach(s t in P[f].Keys)Console.WriteLine(f+", "+t+", "+"ba"[R[f][f+t]]);}}

Dies nutzt die Reduzierung auf maximalen Durchfluss, auf die ich zuvor in den Kommentaren hingewiesen habe. Die Eckpunkte sind

  1. Eine neu erzeugte Quelle Sund Senke T.
  2. Die Partnerschaften.
  3. Die Städte.

Die Kanten sind

  1. Von der Quelle zu jeder Partnerschaft mit Durchflusskapazität 1.
  2. Von jeder Partnerschaft zu jeder Stadt in der Partnerschaft mit Flusskapazität 1.
  3. Von jeder Stadt zur Senke mit einer Durchflusskapazität, die dem Budget dieser Stadt entspricht.

Der Algorithmus ist Ford-Fulkerson mit DFS. Es ist a priori offensichtlich, dass jeder Erweiterungspfad den Fluss um 1 erhöht, so dass die Golfoptimierung zum Entfernen der Berechnung des Pfadflusses keinen negativen Einfluss auf die Leistung hat.

Es gibt andere mögliche Optimierungen, indem Annahmen wie "Die Namen der Eingabedateien werden niemals mit den Namen der Städte übereinstimmen" getroffen werden, aber das ist ein bisschen zweifelhaft, IMO.

Peter Taylor
quelle