Bike Racers

                            Solution in C :

In   C  :





#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

long long *array;
int cmp(const void *a, const void *b){
    long long ia = *(long long *)a;
    long long ib = *(long long *)b;
    return array[ia] < array[ib] ? -1 : array[ia] > array[ib];
}
int isValid(int mbikes, int nmen, int k, int z, long long index[]);

int main() {
    //find the k shortes edges "in the bipartite graph" between men & bikes
    //performance metric is the max distance among the k pairs
    //this is a min max problem, minimizing the max distance
    int nmen,mbikes,kspots;
    scanf("%d %d %d",&nmen,&mbikes,&kspots);
    long men[nmen][2], bikes[mbikes][2];
    for(int i=0;i<nmen;i++){scanf("%ld %ld",&men[i][0],&men[i][1]);}
    for(int i=0;i<mbikes;i++){scanf("%ld %ld",&bikes[i][0],&bikes[i][1]);}
    long long d,dists[mbikes*nmen];
    for(int i=0;i<mbikes;i++){
        for(int j=0;j<nmen;j++){
            d=(bikes[i][0]-men[j][0]);
            dists[i*nmen+j]=d*d;
            d=(bikes[i][1]-men[j][1]);
            dists[i*nmen+j]+=d*d;          
        }
    }
    //sort distances, only really need k smallest from each bike
    //discard those that are larger (but not those that are equal)
    long long index[mbikes*nmen];//use malloc to large size array
    for(long i=0;i<mbikes*nmen;i++){index[i] = i;}
    array = dists;
    qsort(index, mbikes*nmen, sizeof(*index), cmp);
    //for(long i=0;i<mbikes*nmen;i++){printf("%lld ",dists[index[i]]);} printf("\n");
    
    int last=kspots;   
    //do binary search to find out minimum dist that allows a valid assignment
    int left=0, right=mbikes*nmen, width=mbikes*nmen, mid;
    while(width>4){
        width/=2; mid=(left+right)/2; 
        //printf("Check %d\n",mid);
        if(!isValid(mbikes,nmen,kspots,mid,index)){ left=mid; }
        else{right=mid;}
    }
    last=right;
    for (int j=left;j<right;j++){
        //printf("Check %d\n",j);
        if(isValid(mbikes,nmen,kspots,j,index)) {last=j;break;}
    } 
    printf("%lld",dists[index[last-1]]);
    return 0;
}

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 1000
#define oo 1000000000
int n;  // number of nodes
int e;  // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix
int color[MAX_NODES]; // needed for breadth-first search               
int pred[MAX_NODES];  // array to store augmenting path
int max_flow (int source, int sink);
int isValid(int mbikes, int nmen, int k, int z, long long index[]){
    //check if we can pick k unique row/col pairs among the first z
    //this is a matching of cardinality k in the bipartite ii-jj graph
    if(z<k) return 0;
    //capacity rows 0-249, cols 250-499, source as 500, sink as 501
    for(int i=0;i<500;i++){
        for(int j=0;j<500;j++){capacity[i][j]=0;}
    }   
    for(int i=0;i<250;i++){capacity[500][i]=1;}
    for(int i=0;i<250;i++){capacity[250+i][501]=1;}
    for(int i=0;i<z;i++){
        int ii=index[i]/nmen;
        int jj=index[i]%nmen;
        capacity[ii][250+jj]=1;
    }
    n=502; e=z+2; 
    int maxflow=max_flow(500,501);
    //printf("Max flow for z= %d\n",maxflow);
    if(maxflow>=k) return 1;
    else return 0;
}
// below follows Ford-Fulkerson algorithm for max matching via max flow

int min (int x, int y) {
    return x<y ? x : y;  // returns minimum of x and y
}
int head,tail;
int q[MAX_NODES+2];
void enqueue(int x){q[tail] = x; tail++; color[x] = GRAY;}
int dequeue(){int x = q[head]; head++; color[x] = BLACK; return x;}
int bfs (int start, int target) {
    int u,v;
    for (u=0; u<n; u++) { color[u] = WHITE; }   
    head = tail = 0;
    enqueue(start);
    pred[start] = -1;
    while (head!=tail) {
		u = dequeue();
        // Search all adjacent white nodes v. If the capacity
        // from u to v in the residual network is positive, enqueue v.
		for (v=0; v<n; v++) {
			if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0) {
				enqueue(v); pred[v] = u;
			}
		}
    }
    // If the color of the target node is black now, it means that we reached it.
    return color[target]==BLACK;
}
int max_flow (int source, int sink) {
    int i,j,u;
    // Initialize empty flow.
    int max_flow = 0;
    for (i=0; i<n; i++) {
		for (j=0; j<n; j++) {
			flow[i][j] = 0;
		}
    }
    // While there exists an augmenting path, increment the flow along this path.
    while (bfs(source,sink)) {
        // Determine the amount by which we can increment the flow.
		int increment = oo;
		for (u=n-1; pred[u]>=0; u=pred[u]) {
			increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);
		}
        // Now increment the flow.
		for (u=n-1; pred[u]>=0; u=pred[u]) {
			flow[pred[u]][u] += increment; flow[u][pred[u]] -= increment;
		}
		max_flow += increment;
    }
    // No augmenting path anymore. We are done.
    return max_flow;
}
                        

                        Solution in C++ :

In  C++  :





#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
int i,j,n,m,k,x[259],y[259],a[259],b[259],C[259],urm[259],pre[259];
long long p,u,mij,ras,D[259][259];
vector < int > v[259];
int mod(int x)
{
    if(x<0) return -x;
    return x;
}
int cup(int nod)
{
    if(C[nod]==1) return 0;
    C[nod]=1;
    vector < int > :: iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(pre[*it]==0)
        {
            pre[*it]=nod;
            urm[nod]=*it;
            return 1;
        }
    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(cup(pre[*it]))
        {
            pre[*it]=nod;
            urm[nod]=*it;
            return 1;
        }
    return 0;
}
int cuplaj()
{
    int ok=1;
    for(i=1;i<=n;i++)
        C[i]=urm[i]=0;
    for(j=1;j<=m;j++)
        pre[j]=0;
    while(ok)
    {
        ok=0;
        for(i=1;i<=n;i++)
            C[i]=0;
        for(i=1;i<=n;i++)
            if(urm[i]==0) ok+=cup(i);
    }
    ok=0;
    for(i=1;i<=n;i++)
        ok+=(urm[i]>0);
    return ok;
}
bool ok(long long dstmx)
{
    int i;
    for(i=1;i<=n;i++)
        v[i].clear();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(D[i][j]<=dstmx) v[i].push_back(j);
    return (cuplaj()>=k);
}
int main()
{
//freopen("input","r",stdin);
//freopen("output","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&k);
for(i=1;i<=n;i++)
{
    scanf("%d",&x[i]);
    scanf("%d",&y[i]);
}
for(i=1;i<=m;i++)
{
    scanf("%d",&a[i]);
    scanf("%d",&b[i]);
}
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        D[i][j]=1LL*(a[j]-x[i])*(a[j]-x[i])+1LL*(b[j]-y[i])*(b[j]-y[i]);
p=0;
u=10000000000000000;
while(p<=u)
{
    mij=(p+u)/2;
    if(ok(mij))
    {
        ras=mij;
        u=mij-1;
    }
    else p=mij+1;
}
printf("%lld\n",ras);
return 0;
}
                    

                        Solution in Java :

In   Java :







import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class Solution {
	static BufferedReader in = new BufferedReader(new InputStreamReader(
			System.in));
	static StringBuilder out = new StringBuilder();

	private static Node source;
	private static Node sink;
	private static Node[] bikers;
	private static Node[] bikes;
	
	
	public static void main(String[] args) throws IOException {
		String line = in.readLine();
		String[] data = line.split("\\s+");
		int numBikers = Integer.parseInt(data[0]);
		int numBikes = Integer.parseInt(data[1]);
		int numRequired = Integer.parseInt(data[2]);

		source = new Node();
		sink = new Node(true);
		bikers = new Node[numBikers];
		bikes = new Node[numBikes];
		
		Coordinate[] bikerPos = new Coordinate[numBikers];
		
		for(int i = 0; i < numBikers; i ++)
		{
			bikers[i] = new Node();
			source.addConnection(bikers[i]);
			line = in.readLine();
			data = line.split("\\s+");
			bikerPos[i] = new Coordinate(Integer.parseInt(data[0]), Integer.parseInt(data[1]));
		}
		
		ArrayList<BikerBikeDistance> bbd = new ArrayList<>();
		
		for(int j = 0; j < numBikes; j ++)
		{
			bikes[j] = new Node();
			bikes[j].addConnection(sink);
			line = in.readLine();
			data = line.split("\\s+");
			int bx = Integer.parseInt(data[0]);
			int by = Integer.parseInt(data[1]);
			for(int i = 0; i < numBikers; i ++)
			{
				bbd.add(new BikerBikeDistance(i, j, getCost(bx, by, bikerPos[i].x, bikerPos[i].y)));
			}
		}
		
		Collections.sort(bbd);
		
		
		int total = 0;
		long dist = 0;
		for(int i = 0; total < numRequired; i ++)
		{
			BikerBikeDistance cbbd = bbd.get(i);
			dist = cbbd.cost;
			bikers[cbbd.biker].addConnection(bikes[cbbd.bike]);
			if(source.dfsAndReverse(i))
			{
				total ++;
			}
		}
		System.out.println(dist);
	}
	
	
	private static long getCost(long x1, long y1, long x2, long y2)
	{
		return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	}
	
	private static class Coordinate
	{
		final int x;
		final int y;
		
		public Coordinate(int x, int y)
		{
			this.x = x;
			this.y = y;
		}
	}
	
	private static class BikerBikeDistance implements Comparable<BikerBikeDistance>
	{
		final int biker;
		final int bike;
		final long cost;
		String name;
		
		public BikerBikeDistance(int biker, int bike, long cost)
		{
			this.biker = biker;
			this.bike = bike;
			this.cost = cost;
		}

		@Override
		public int compareTo(BikerBikeDistance o) {
			if(cost < o.cost)
			{
				return -1;
			}
			if(cost > o.cost)
			{
				return 1;
			}
			return 0;
		}
	}
	
	private static class Node
	{
		private LinkedList<Node> connections;
		private int visitedNum;
		private boolean isTerminus;
		
		public Node()
		{
			connections = new LinkedList<Node>();
			visitedNum = -999;
			isTerminus = false;
		}
		
		public Node(boolean terminus)
		{
			connections = new LinkedList<Node>();
			visitedNum = -999;
			isTerminus = terminus;
		}
		
		public int getVisited()
		{
			return visitedNum;
		}
		
		public void addConnection(Node n)
		{
			connections.add(n);
		}
		
		public boolean dfsAndReverse(int v)
		{
			if(isTerminus)
			{
				return true;
			}
			visitedNum = v;
			Iterator<Node> i = connections.iterator();
			while(i.hasNext())
			{
				Node n = i.next();
				if(n.getVisited()!=v)
				{
					if(n.dfsAndReverse(v))
					{
						n.addConnection(this);
						i.remove();
						return true;
					}
				}
			}
			return false;
		}
	}
}
                    

                        Solution in Python : 
                            
In   Python3  :








# from sets import Set
def bipartiteMatch(graph):
    '''Find maximum cardinality matching of a bipartite graph (U,V,E).
    The input format is a dictionary mapping members of U to a list
    of their neighbors in V.  The output is a triple (M,A,B) where M is a
    dictionary mapping members of V to their matches in U, A is the part
    of the maximum independent set in U, and B is the part of the MIS in V.
    The same object may occur in both U and V, and is treated as two
    distinct vertices if this happens.'''
    
    # initialize greedy matching (redundant, but faster than full search)
    matching = {}
    for u in graph:
        for v in graph[u]:
            if v not in matching:
                matching[v] = u
                break
    
    while 1:
        # structure residual graph into layers
        # pred[u] gives the neighbor in the previous layer for u in U
        # preds[v] gives a list of neighbors in the previous layer for v in V
        # unmatched gives a list of unmatched vertices in final layer of V,
        # and is also used as a flag value for pred[u] when u is in the first layer
        preds = {}
        unmatched = []
        pred = dict([(u,unmatched) for u in graph])
        for v in matching:
            del pred[matching[v]]
        layer = list(pred)
        
        # repeatedly extend layering structure by another pair of layers
        while layer and not unmatched:
            newLayer = {}
            for u in layer:
                for v in graph[u]:
                    if v not in preds:
                        newLayer.setdefault(v,[]).append(u)
            layer = []
            for v in newLayer:
                preds[v] = newLayer[v]
                if v in matching:
                    layer.append(matching[v])
                    pred[matching[v]] = v
                else:
                    unmatched.append(v)
        
        # did we finish layering without finding any alternating paths?
        if not unmatched:
            unlayered = {}
            for u in graph:
                for v in graph[u]:
                    if v not in preds:
                        unlayered[v] = None
            return (matching,list(pred),list(unlayered))

        # recursively search backward through layers to find alternating paths
        # recursion returns true if found path, false otherwise
        def recurse(v):
            if v in preds:
                L = preds[v]
                del preds[v]
                for u in L:
                    if u in pred:
                        pu = pred[u]
                        del pred[u]
                        if pu is unmatched or recurse(pu):
                            matching[v] = u
                            return 1
            return 0

        for v in unmatched: recurse(v)

def main():
    N, M, K = map(int, input().split())
    bikers = []
    bikes = []
    for i in range(N):
        a, b = map(int, input().split())
        bikers.append((a,b))
    for i in range(M):
        a, b = map(int, input().split())
        bikes.append((a,b))

    edges = []
    for (a,b) in bikers:
        for (c,d) in bikes:
            dist = (a - c)**2 + (b - d)**2
            edges.append((dist,(a,b),(c,d)))

    edges = sorted(edges, reverse = True)
    removed_bikers = 0
    removed_bikes = 0
    biker_hits = dict([(biker, 0) for biker in bikers])
    bike_hits = dict([(bike, 0) for bike in bikes])
    # biker_critical = False
    # bike_critical = False

    bikers = set(bikers)
    bikes = set(bikes)

    # G = dict([(biker, [bike for bike in bikes]) for biker in bikers])
    # (matching, A, B) = bipartiteMatch(G)
    # matching = Set(matching)
    # print "matching = " + str(matching)
    # print "len(matching) = " + str(len(matching))
    # print edges
    # for i in range(len(edges)):
    neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
    G = dict([(biker, neighbors[biker]) for biker in bikers])
    (matching, A, B) = bipartiteMatch(G)
    matching_pairs = set([(bike, matching[bike]) for bike in matching])
    # print "len(matching) = " + str(len(matching))

    
    for (dist, biker, bike) in edges:
        # (dist, biker, bike) = edges[i]
        biker_hits[biker] += 1
        bike_hits[bike] += 1
        neighbors[biker].remove(bike)

        # if len(matching) >= K:
        if (bike, biker) in matching_pairs:
            G = dict([(biker, neighbors[biker]) for biker in bikers])
            (matching, A, B) = bipartiteMatch(G)
            matching_pairs = set([(bike, matching[bike]) for bike in matching])
            # print "len(matching) = " + str(len(matching))
            if len(matching.keys()) < K:
                print(dist)
                break

        if biker_hits[biker] == M:
            bikers.remove(biker)

if __name__ == "__main__":    
    main()