BWInf 2011, question 5: Twin towns
C#, 1016 992 916 chars

Takes 4 seconds for me on the large test set; performance can easily be improved a lot by making X a HashSet&lt;s&gt; rather than a List&lt;s&gt;.

using System;using System.Collections.Generic;using System.IO;using System.Linq;using
s=System.String;class D&lt;T&gt;:Dictionary&lt;s,T&gt;{}class E:D&lt;int&gt;{static void Main(s[]x){s
S="",T="&gt;",l;s[]b;D&lt;E&gt;R=new D&lt;E&gt;(),P=new D&lt;E&gt;();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&lt;s&gt;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)&amp;R[l][t]&gt;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]]);}}


This uses the reduction to max flow which I hinted at earlier in comments. The vertices are


A newly generated source S and sink T.
The partnerships.
The cities.


The edges are


From the source to each partnership with flow capacity 1.
From each partnership to each city in the partnership with flow capacity 1.
From each city to the sink with flow capacity equal to that city's budget.


The algorithm is Ford-Fulkerson with DFS. It is obvious a priori that each augmenting path will increase the flow by 1, so the golfing optimisation of removing the computation of the path's flow has no negative effect on performance.

There are other possible optimisations by making assumptions such as "The names of the input files will never be the same as the names of the cities", but that's a bit iffy IMO.