Submission #1321709

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <functional>
using namespace std;

#define int long long
static const int INF = 1e13;
struct MinCostFlow {
	struct E {
		//to,容量,コスト,逆辺のindex
		int to, cap, cost, rev;
		E(int t, int ca, int co, int r) {
			to = t;
			cap = ca;
			cost = co;
			rev = r;
		}
	};

	//最大頂点数
	int V;
	vector<vector<E>>G;
	MinCostFlow(int v) {
		V = v;
		G.resize(V);
	}

	//有向辺
	inline void add_edge(int from, int to, int cap, int cost) {
		if (from == to)return;
		E e = E(to, cap, cost, G[to].size());
		E ee = E(from, 0, -cost, G[from].size());
		G[from].push_back(e);
		G[to].push_back(ee);
	}

	//コストを距離とみる
	//コスト,最小コスト
	vector<int>dist, mindist;
	//パス復元用
	vector<int>pre_v, pre_i;

	//始点から各頂点までの最小コスト
	void dijkstra(int s) {
		priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > que;
		dist.assign(V, INF);
		dist[s] = 0;
		que.push(pair<int,int>(0,s));
		while (!que.empty()) {
			pair<int,int> p = que.top(); que.pop();
			int v = p.second;
			if (dist[v] < p.first)continue;

			for (int i = 0; i < G[v].size(); i++) {
				E &e = G[v][i];
				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + mindist[v] - mindist[e.to]) {
					dist[e.to] = dist[v] + e.cost + mindist[v] - mindist[e.to];
					pre_v[e.to] = v;
					pre_i[e.to] = i;
					que.push(pair<int,int>(dist[e.to], e.to));
				}
			}
		}
	}

	//最小費用を返す
	int min_cost_flow(int s, int t, int flow) {
		int cost = 0;
		mindist.resize(V);
		pre_v.resize(V);
		pre_i.resize(V);

		//フローを流しつくすまで
		while (flow > 0) {
			dijkstra(s);
			//もう流せなかったら
			if (dist[t] == INF)return cost;

			//最小コストの更新
			for (int v = 0; v < V; v++)mindist[v] += dist[v];

			//最小コストパス上の最大流
			int f = flow;
			for (int v = t; v != s; v = pre_v[v]) {
				f = min(f, G[pre_v[v]][pre_i[v]].cap);	
			}
			flow -= f;

			//費用の更新
			cost += f * mindist[t];

			//容量の更新
			for (int v = t; v != s; v = pre_v[v]) {
				E& e = G[pre_v[v]][pre_i[v]];
				E& ee = G[v][e.rev];
				e.cap -= f;
				ee.cap += f;
			}
		}

		return cost;
	}
};

signed main() {
	int N; cin >> N;
	vector<int>A(N), B(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}

	MinCostFlow mnc(2*N+2);

	for (int i = 0; i < N; i++) {
		mnc.add_edge(0, i + 1, A[i], 0);
		mnc.add_edge(N+i+1, 2*N+1, B[i], 0);
		for (int j = 0; j < N; j++) {
			mnc.add_edge(i+1,N+j+1,A[i],abs(i-j));
		}
	}

	int ans = mnc.min_cost_flow(0,2*N+1,INF);

	cout << ans << endl;
}

Submission Info

Judge Result