結果

問題 No.119 旅行のツアーの問題
ユーザー shobonvipshobonvip
提出日時 2024-04-02 08:40:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 3,298 bytes
コンパイル時間 3,368 ms
コンパイル使用メモリ 228,732 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-30 23:04:38
合計ジャッジ時間 4,217 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 2 ms
6,820 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 4 ms
6,820 KB
testcase_17 AC 2 ms
6,820 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 2 ms
6,816 KB
testcase_20 AC 3 ms
6,820 KB
testcase_21 AC 3 ms
6,816 KB
testcase_22 AC 3 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/maxflow>

template <typename T>
struct MoyasuUmeru {
	int n, s, t;
	T geta;
	vector<vector<T>> cost;
	atcoder::mf_graph<T> graph;

	MoyasuUmeru(int n):
		n(n),
		s(n),
		t(n+1),
		geta(0),
		cost(2),
		graph(0) {
			graph = atcoder::mf_graph<T>(n+2);
			cost[0].resize(n);
			cost[1].resize(n);
		}

	void add_cost(int i, int state, T val){
		cost[state][i] += val;
	}

	void add_constraint(int x, int y, const vector<vector<T>> &cs){
		T a = cs[0][0];
		T b = cs[0][1];
		T c = cs[1][0];
		T d = cs[1][1];
		geta += a;
		add_cost(x, 1, c - a);
		add_cost(y, 1, d - c);
		assert(b + c - a - d >= 0);
		graph.add_edge(x, y, b + c - a - d);
	}

	pair<T, vector<int>> solve(){
		for (int i=0; i<n; i++){
			if (cost[0][i] <= cost[1][i]){
				graph.add_edge(s, i, cost[1][i] - cost[0][i]);
				geta += cost[0][i];
			}else{
				graph.add_edge(i, t, cost[0][i] - cost[1][i]);
				geta += cost[1][i];
			}
		}
		T ret1 = geta + graph.flow(s, t);
		vector<bool> result = graph.min_cut(s);
		vector<int> ret2(n);
		for (int i=0; i<n; i++){
			if (result[i]){
				ret2[i] = 1;
			}
		}
		return pair(ret1, ret2);
	};
};

template<typename T>
struct KvaluedMoyasuUmeru {
	int n;
	int alls;
	vector<int> k;
	MoyasuUmeru<T> mf;
	vector<int> offset;
	T geta;

	KvaluedMoyasuUmeru(const vector<int> &kk, T INF):
		k(kk), n((int)kk.size()), alls(0), geta(0), mf(0), offset(n) {
			for (int i=0; i<n; i++){
				assert(k[i] >= 1);
			}
			for (int i=0; i<n-1; i++){
				offset[i+1] = offset[i] + k[i] - 1;
			}
			alls = offset[n-1] + k[n-1] - 1;
			mf = MoyasuUmeru<T>(alls);
			for (int i=0; i<n; i++){
				for (int j=0; j<k[i]-2; j++){
					mf.graph.add_edge(offset[i] + j + 1, offset[i] + j, INF);
				}
			}
		}
	
	void add_1v(int i, const vector<T> &val){
		assert((int)val.size() == k[i]);
		geta += val[k[i]-1];
		for (int j=0; j<k[i]-1; j++){
			mf.add_cost(offset[i] + j, 1, val[j] - val[j+1]);
		}
	}

	void add_2v(int x, int y, const vector<vector<T>> &val){
		assert((int)val.size() == k[x]);
		assert((int)val[0].size() == k[y]);
		vector<T> add_to_x(k[x]);
		vector<T> add_to_y(k[y]);
		for (int i=0; i<k[x]; i++){
			add_to_x[i] = val[i][0];
		}
		for (int i=0; i<k[y]; i++){
			add_to_y[i] = val[0][i];
		}
		add_1v(x, add_to_x);
		add_1v(y, add_to_y);
		geta -= val[0][0];
		for (int i=0; i<k[x]-1; i++){
			for (int j=0; j<k[y]-1; j++){
				mf.add_constraint(
					offset[x]+i,
					offset[y]+j,
					{
						{val[i+1][j+1] - val[i][j+1] - val[i+1][j] + val[i][j], 0},
						{0, 0}
					}
				);
			}
		}
	}

	pair<T, vector<int>> solve() {
		auto [old1, old2] = mf.solve();
		T ret1 = old1 + geta;
		vector<int> ret2(n);
		for (int i=0; i<n; i++){
			ret2[i] = 0;
			for (int j=0; j<k[i]-1; j++){
				if (old2[offset[i]+j] == 1){
					ret2[i] = j+1;
				}
			}
		}
		return pair(ret1, ret2);
	}
};


typedef long long ll;
int main(){
	int n; cin >> n;
	KvaluedMoyasuUmeru<ll> mf(vector<int>(n, 3), (ll)1e9);

	vector<ll> b(n), c(n);
	for (int i=0; i<n; i++){
		cin >> b[i] >> c[i];
		mf.add_1v(i, {-c[i], 0, -b[i]});
	}

	int m; cin >> m;
	for (int i=0; i<m; i++){
		int d, e; cin >> d >> e;
		mf.add_2v(d, e,
			{
				{0, 0, 0},
				{0, 0, 0},
				{(ll)1e9, 0, 0}
			}
		);	
	}

	auto [x1, x2] = mf.solve();
	cout << - x1 << '\n';
}
0