結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー hos.lyric
提出日時 2015-02-18 05:52:58
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 3,749 bytes
コンパイル時間 1,013 ms
コンパイル使用メモリ 124,544 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-12 02:23:26
合計ジャッジ時間 1,790 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import core.thread;
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex;

//	Input
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { tokens = readln.split; if (tokens.empty && stdin.eof) throw new EOFException; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return to!int(readToken); }
long readLong() { return to!long(readToken); }
real readReal() { return to!real(readToken); }

//	chmin/chmax
void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

//	Pair
struct Pair(S, T) {
	S x; T y;
	int opCmp(    const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	int opCmp(ref const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	string toString() const { return "(" ~ to!string(x) ~ ", " ~ to!string(y) ~ ")"; }
}
auto pair(S, T)(inout(S) x, inout(T) y) { return Pair!(S, T)(x, y); }

//	Array
int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = as.length; for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <  val); }); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <= val); }); }
T[] unique(T)(in T[] as) { T[] bs; foreach (a; as) if (bs.empty || bs[$ - 1] != a) bs ~= a; return bs; }

class MaxFlow(CAPA) {
	static immutable CAPA wEPS = 0;
	static immutable CAPA wINF = 1001001001;
	int n, m;
	int[][] g;
	int[] zu;
	CAPA[] capa;
	CAPA tof;
	int[] lev, see, que;
	this (int n) {
		this.n = n; m = 0; g = new int[][n]; zu = null; capa = null;
		lev = new int[n]; see = new int[n]; que = new int[n];
	}
	void ae(int u, int v, CAPA w0, CAPA w1 = 0) {
		g[u] ~= m; zu ~= v; capa ~= w0; ++m;
		g[v] ~= m; zu ~= u; capa ~= w1; ++m;
	}
	CAPA augment(int src, int ink, CAPA flo) {
		if (src == ink) return flo;
		foreach (i; g[src][see[src] .. $]) {
			if (capa[i] > wEPS && lev[src] < lev[zu[i]]) {
				CAPA f = augment(zu[i], ink, min(flo, capa[i]));
				if (f > wEPS) {
					capa[i] -= f; capa[i ^ 1] += f; return f;
				}
			}
			++see[src];
		}
		return 0;
	}
	bool dinic(int src, int ink, CAPA flo = wINF) {
		for (tof = 0; tof + wEPS < flo; ) {
			int[] q;
			lev[] = -1;
		dinicBFS:
			for (lev[src] = 0, q ~= src; !q.empty; ) {
				int u = q.front; q.popFront;
				foreach (i; g[u]) {
					int v = zu[i];
					if (capa[i] > wEPS && lev[v] == -1) {
						lev[v] = lev[u] + 1; q ~= v;
						if (v == ink) break dinicBFS;
					}
				}
			}
			if (lev[ink] == -1) return false;
			see[] = 0;
			for (; ; ) {
				CAPA f = augment(src, ink, flo - tof);
				if (f <= wEPS) break;
				tof += f;
			}
		}
		return true;
	}
}

int N;
int[] B, C;
int M;
int[] D, E;

void main(string[] args) {
	try {
	for (; ; ) {
		N = readInt;
		B = new int[N];
		C = new int[N];
		foreach (u; 0 .. N) {
			B[u] = readInt;
			C[u] = readInt;
		}
		M = readInt;
		D = new int[M];
		E = new int[M];
		foreach (i; 0 .. M) {
			D[i] = readInt;
			E[i] = readInt;
		}
		
		int ans;
		ans += B.reduce!((a, b) => a + b);
		ans += C.reduce!((a, b) => a + b);
		
		auto mf = new MaxFlow!(int)(2 + N * 2);
		int L(int u) { return 2 + u * 2 + 0; }
		int R(int u) { return 2 + u * 2 + 1; }
		foreach (u; 0 .. N) {
			mf.ae(0, L(u), B[u]);
			mf.ae(L(u), R(u), mf.wINF);
			mf.ae(R(u), 1, C[u]);
		}
		foreach (i; 0 .. M) {
			mf.ae(L(D[i]), R(E[i]), mf.wINF);
		}
		mf.dinic(0, 1);
		ans -= mf.tof;
		
		writeln(ans);
		
	}
	} catch (EOFException) {}
}
0