Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-17SRM371, SRM372 (Practice)

SRM 372 RadarGuns

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

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

  • え、何これ
    • 罰金の最小値は最小費用流そのもの。
    • 得られる罰金の最大値は各辺のコストを(適当にでかい数 - 罰金)として、(適当にでかい数) * 車の数 - 最小費用流 とすればいい
  • ライブラリをはっつけゲーでした
    • 今のするめ環境ではこんな見え見えなのは出たりしないはず・・・
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 RadarGuns {

	public class State implements Comparable {
		int dist;
		int now;
		public State(int _n, int _d) {
			now = _n;
			dist = _d;
		}
		public int compareTo(Object arg0) {
			State a = (State) arg0;
			return dist - a.dist;
		}
	}
	public class Edge {
		int to;
		int cap;
		int rev;
		int cost;
		public Edge(int _to, int _cap, int _cost, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
			cost = _cost;
		}
	}
	public int INF = 10000000;
	public int V;
	public int[] h;
	public int[] dist;
	public int[] prevv, preve;
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		dist = new int[size];
		prevv = new int[size];
		preve = new int[size];
		h = new int[size];
		V = size;
		
	}
	public void edge(int from, int to, int cap, int cost) {
		graph.get(from).add(new Edge(to, cap, cost, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, -cost, graph.get(from).size() - 1));
	}
	public int min_cost_flow(int s, int t, int f) {
		int res = 0;
		Arrays.fill(h, 0);
		while (f > 0) {
			Queue<State> q = new PriorityQueue<State>(10000);
			Arrays.fill(dist, INF);
			dist[s] = 0;
			q.add(new State(s, 0));
			while (q.size() >= 1) {
				State stat = q.poll();
				int v = stat.now;
				if (dist[v] < stat.dist) {
					continue;
				}
				for (int i = 0 ; i < graph.get(v).size() ; i++) {
					Edge e = graph.get(v).get(i);
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						q.add(new State(e.to, dist[e.to]));
					}
				}
			}
			if (dist[t] == INF) {
				return -1;
			}
			for (int v = 0 ; v < V ; v++) {
				h[v] += dist[v];
			}
			int d = f;
			for (int v = t ; v != s ; v = prevv[v]) {
				d = Math.min(d, graph.get(prevv[v]).get(preve[v]).cap);
			}
			f -= d;
			res += d * h[t];
			for (int v = t ; v != s ; v = prevv[v]) {
				Edge e = graph.get(prevv[v]).get(preve[v]);
				e.cap -= d;
				graph.get(v).get(e.rev).cap += d;
			}
		}
		return res;
	}
	
	public int[] getRange(int[] enterTimes, int[] exitTimes, int speedTime, int fineCap) {
		int len = enterTimes.length;
		int[] ans = new int[2];
		for (int d = 0 ; d <= 1 ; d++) {
			init(len*2+2);
			int from = len*2;
			int to = len*2+1;
			for (int i = 0 ; i < len ; i++) {
				edge(from, i, 1, 0);
				edge(i+len, to, 1, 0);
			}
			for (int i = 0 ; i < len ; i++) {
				for (int j = 0 ; j < len ; j++) {
					int enter = enterTimes[i];
					int exit = exitTimes[j];
					int spd = exit - enter;
					if (spd >= 1) {
						int fine = 0;
						if (spd < speedTime) {
							fine = Math.min(fineCap, (speedTime - spd) * (speedTime - spd));
						}
						if (d == 1) {
							fine = 1000000 - fine;
						}
						edge(i, len+j, 1, fine);
					}
				}
			}
			ans[d] = min_cost_flow(from, to, len);
			if (d == 1) {
				ans[1] = 1000000 * len - ans[1];
			}
		}
		if (ans[0] == -1) {
			return new int[]{};
		}
		return ans;
	}
}