Facility Locations

Introduction

This asks you to select k of m (100) facility locations such that each of n (100) clients has a 0-length path to one of the k facilities.

Solutions

Greedy

Consider the fancy equation c(ij) <= c(i'j) + c(i'j') + c(ij'). This equation implies that if I have 0 distance to some node, and non-zero distance to some other node, then any other node with 0 distance to this node also has non-zero distance to that other node. (hint: put the "non-zero" distance as c(ij), and the equation no longer balances). This means that if some node has multiple facilities which serve it, then those facilities will serve all the same nodes...so we can greedily select whichever one, and know that it doesn't make any difference.

Go though the nodes, and when you find one uncovered by a facility, select that facility and mark all other nodes that facility serves as covered.

Note: this is equivalent to realizing that any facility/node groups have a complete bipartite matching, and thus simply checking that there are k connected components (assigning a facility to each one)

Code

Solution - Java

import java.util.*;
public class d {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new d().go();
	}
	private void go() {
		int m=in.nextInt(),n=in.nextInt(),k=in.nextInt();
		int[][] d=new int[m][n];
		for(int i=0;i<m;i++)for(int j=0;j<n;j++)d[i][j]=in.nextInt();
		HashSet<Integer>done=new HashSet<Integer>();
		for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(d[i][j]==0&&!done.contains(j)){//found uncovered node with length 0
			if(k==0){//oops already used our allotment
				System.out.println("no");
				System.exit(0);
			}
			k--;
			for(;j<n;j++)if(d[i][j]==0)done.add(j);//cover any nodes left here
		}
		if(done.size()==n)System.out.println("yes");
		else System.out.println("no");
	}
}