Codeforces Round #144 (Div. 2 only) (No. 237)

DIV1なのでNon rated。
Cで、二分探索ミスった。
見つからないかを確認したい時は、最後にlをチェックするのがいい。
Eは最後に最小費用流っぽいなと思えた。が、時間切れ。
まあ今回はいいけども、本番ではしっかりしたいね。
Spaghetti Source さんの最小費用流が負のコストに対応していない事が判明したので(今まで気づかなかった！気づいてよかった)、ライブラリを新しくした。
アルゴリズムを理解せずに使ってるからこういうことになるんだ！
以下その新しいコード(今回のCodeForces EでACした(だけだから信頼性は十分ではない)(その後に少し書き換えたが))

typedef int Weight;
struct Edge {
  int src, dst;
  Weight capacity, cost;
  Edge(int src_, int dst_, Weight capacity_, Weight cost_) :
    src(src_), dst(dst_), capacity(capacity_), cost(cost_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void createRev(const Graph& g, Graph &r) {
	r.assign(g.size(), Edges());
	each(i, g) each(j, *i) {
		r[j->src].pb(*j);
		r[j->dst].pb(Edge(j->dst, j->src, 0, -j->cost));
	}
}
pair<Weight, Weight> minimumCostFlow(const Graph &g_, int s, int t, Weight f){
	Graph g; createRev(g_, g);
	int n = g.size();
	vector<Weight> dist(n);
	vi prev(n);
	Matrix capacity(n, Array(n)), flow(n, Array(n));
	rep(i, n) each(e, g[i])
		capacity[e->src][e->dst] += e->capacity;
	pair<Weight, Weight> total = mp(0, 0);	// (cost, flow)

	while(f > 0){
		fill(all(dist), INF); dist[s] = 0;
		bool update;
		do {
			update = false;
			rep(u, n) if(dist[u] != INF) {
				each(e, g[u]) {
					int v = e->dst; Weight cost = e->cost;
					if(capacity[u][v] - flow[u][v] > 0 &&
					   dist[v] > dist[u] + cost){
						dist[v] = dist[u] + cost;
						prev[v] = u;
						update = true;
					}
				}
			}
		} while(update);
		if(dist[t] == INF) break;	//流しきれない時
		
		int d = f;
		for(int v = t; v != s; v = prev[v])
			d = min(d, capacity[prev[v]][v] - flow[prev[v]][v]);
		f -= d; total.first += d * dist[t]; total.second += d;
		for(int v = t; v != s; v = prev[v])
			flow[prev[v]][v] += d; flow[v][prev[v]] -= d;
	}
	return total;
}