ECR029F: Almost Permutation

http://codeforces.com/contest/863/problem/F

フローと言われちゃえばねぇ…。

まず配列の各iについてA[i]以上B[i]以下ではならないという条件を求める。B[i] < A[i]ならもちろん-1を返す。
それからはフローで値を求めるのだが、区間N個にN * 2 + j(0 <= j < N)という番号を振り当てると、
N * 2 + jからA[i] <= x <= B[i]を満たすxに辺を張り、xには1流すとコスト1,2流すとコスト3...k流すとコスト2*k+1になるように辺を張る。
そうすると、xにk流れた時コストはk^2になるのであとはこれの最小費用流を求めればよい。

int N, Q;
int A[MAX_N], B[MAX_N];

int cnt[MAX_N];

void solve() {
	cin >> N >> Q;
	rep(i, 0, N) B[i] = N - 1;
	while(Q--) {
		int q, a, b, c;
		cin >> q >> a >> b >> c;
		a--; b--; c--;
		if(q == 1) {
			for(int i = a; i <= b; i++) MAX(A[i], c);
		}
		else {
			for(int i = a; i <= b; i++) MIN(B[i], c);
		}
	}
	rep(i, 0, N) {
		if(B[i] < A[i]) {
			cout << -1 << "\n";
			return;
		}
	}
	MCC::init(N * 3 + 1);
	int t = N * 3;
	rep(i, 0, N) {
		MCC::set_d(N * 2 + i, -1);
		for(int j = A[i]; j <= B[i]; j++) {
			MCC::add_edge(N * 2 + i, j, inf, 0);
			MCC::add_edge(j, j + N, 1, cnt[j] * 2 + 1); cnt[j]++;
			MCC::add_edge(j + N, t, inf, 0);
		}
	}
	MCC::set_d(t, N);
	cout << MCC::get() << "\n";
}

循環最小費用流(各点について流量を設定できるヤツ)を使ったが、普通に下限設定できる最小費用流ライブラリが欲しいと思った。(こなみ)