Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-04SRM349 (Practice)

SRM 348 RailwayTickets

|  SRM 348 RailwayTickets - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 348 RailwayTickets - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7760

  • 蟻本第二版p220と同じ問題。
    • そのままやるとTLEするが、座標圧縮するとうまくいく。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class RailwayTickets {
	// 最小費用流のコードは省略

	class P {
		int from, to;
		P(String data) {
			String[] ft = data.split("-");
			from = Integer.valueOf(ft[0]);
			to = Integer.valueOf(ft[1]);
		}
	}

	public int minRejects(String[] travel, int seats) {
		int len = travel.length;
		List<P> p = new ArrayList<P>();
		for (int i = 0 ; i < len ; i++) {
			String[] data = travel[i].split(" ");
			int dlen = data.length;
			for (int j = 0 ; j < dlen ; j++) {
				p.add(new P(data[j]));
			}
		}
		
		int max = 0;
		int[] tcnt = new int[10001];
		for (int i = 0 ; i < p.size() ; i++) {
			P pas = p.get(i);
			tcnt[pas.from]++;
			tcnt[pas.to]++;
		}
		
		int[] idmap = new int[10001];
		int idcnt = 1;
		for (int i = 1 ; i <= 10000 ; i++) {
			if (tcnt[i] >= 1) {
				idmap[i] = idcnt;
				idcnt++;
			}
		}
		
		int start = 0;
		int goal = 10001;
		init(10002);
		
		edge(start, 1, seats, 0);
		edge(idcnt-1, goal, seats, 0);
		for (int i = 1 ; i < idcnt ; i++) {
			edge(i, i+1, INF, 0);
		}
		
		for (int i = 0 ; i < p.size() ; i++) {
			int from = idmap[p.get(i).from];
			int to = idmap[p.get(i).to];
			edge(to, from, 1, 1);
			edge(start, to, 1, 0);
			edge(from, goal, 1, 0);
		}
		
		return min_cost_flow(start, goal, seats+p.size());
	}
}