結果

問題 No.3306 Life is Easy?
ユーザー cho435
提出日時 2025-10-08 00:26:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,928 bytes
コンパイル時間 4,487 ms
コンパイル使用メモリ 265,252 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-08 00:26:44
合計ジャッジ時間 13,873 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 7 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

using mint = atcoder::modint998244353;

// https://github.com/drken1215/algorithm/blob/master/GraphNetworkFlow/min_cost_b_flow_by_network_simplex_method.cpp
// Network Simplex Method
template <class FLOW, class COST> struct NetworkSimplex {
	struct Edge {
		int from, to;
		FLOW cap;
		COST cost;
		friend ostream& operator<<(ostream& s, const Edge& e) {
			return s << e.from << " -> " << e.to << " (" << e.cap << ", "
					 << e.cost << ")";
		}
	};
	struct Parent {
		int p, e;
		FLOW up, down;
	};

	// inner values
	int N, M;
	vector<Edge> edges;
	vector<FLOW> lowers;  // for edge i
	vector<FLOW> dss;	  // for node v (demand and supply)

	// intermediate results
	int BUCKET_SIZE, MINOR_LIMIT;
	vector<Parent> parents;
	vector<int> depth, nex, pre, candidates;

	// results
	bool feasible;
	COST total_cost;
	vector<FLOW> flows;
	vector<COST> pots;

	// constructor
	explicit NetworkSimplex(int n = 0) : N(n), dss(n) {
	}

	// debugger
	friend ostream& operator<<(ostream& s, const NetworkSimplex& ns) {
		s << "feasibility: " << (ns.feasible ? "true" : "false") << '\n';
		s << "optimal value: " << ns.total_cost << '\n';
		for (int i = 0; i < ns.M; i += 2) {
			auto e = ns.edges[i];
			s << e.from << " -> " << e.to << ": " << ns.flows[i / 2]
			  << " (remained cap: " << e.cap << ", cost: " << e.cost << ")\n";
		}
		for (int v = 0; v < ns.N; v++)
			cout << "node " << v << ": " << ns.pots[v] << '\n';
		return s;
	}

	// setter
	void add_edge(int from, int to, FLOW lower, FLOW upper, COST cost) {
		edges.push_back({from, to, upper - lower, cost});
		edges.push_back({to, from, 0, -cost});
		lowers.push_back(lower);
		dss[from] -= lower;
		dss[to] += lower;
		M = (int)edges.size();
	}
	void add_ds(int v, FLOW ds) {
		assert(v >= 0 && v < N);
		dss[v] += ds;
	}

	// solver
	pair<bool, COST> solve() {
		BUCKET_SIZE = max(int(sqrt(double(M)) * 0.2), 10);
		MINOR_LIMIT = max(int(BUCKET_SIZE * 0.1), 3);
		precompute();
		candidates.reserve(BUCKET_SIZE);
		int ei = 0;
		while (true) {
			for (int i = 0; i < MINOR_LIMIT; i++)
				if (!minor()) break;
			COST best = 0;
			int best_ei = -1;
			candidates.clear();
			for (int i = 0; i < (int)edges.size(); i++) {
				if (edges[ei].cap) {
					COST clen = edges[ei].cost + pots[edges[ei ^ 1].to] -
								pots[edges[ei].to];
					if (clen < 0) {
						if (clen < best) best = clen, best_ei = ei;
						candidates.push_back(ei);
						if ((int)candidates.size() == BUCKET_SIZE) break;
					}
				}
				ei++;
				if (ei == (int)edges.size()) ei = 0;
			}
			if (candidates.empty()) break;
			push_flow(best_ei);
		}
		if (!postcompute()) return {false, COST(-1)};
		else return {true, total_cost};
	}

	void connect(int a, int b) {
		nex[a] = b, pre[b] = a;
	}

	void precompute() {
		pots.assign(N + 1, 0);
		parents.resize(N), depth.assign(N + 1, 1);
		nex.assign((N + 1) * 2, 0), pre.assign((N + 1) * 2, 0);
		COST inf_cost = 1;
		for (int i = 0; i < M; i += 2) {
			inf_cost += (edges[i].cost >= 0 ? edges[i].cost : -edges[i].cost);
		}
		edges.reserve(M + N * 2);
		for (int i = 0; i < N; i++) {
			if (dss[i] >= 0) {
				edges.push_back({i, N, 0, inf_cost});
				edges.push_back({N, i, dss[i], -inf_cost});
				pots[i] = -inf_cost;
			} else {
				edges.push_back({i, N, -dss[i], -inf_cost});
				edges.push_back({N, i, 0, inf_cost});
				pots[i] = inf_cost;
			}
			int e = (int)edges.size() - 2;
			parents[i] = {N, e, edges[e].cap, edges[e ^ 1].cap};
		}
		depth[N] = 0;
		for (int i = 0; i < N + 1; i++) connect(i * 2, i * 2 + 1);
		for (int i = 0; i < N; i++)
			connect(i * 2 + 1, nex[N * 2]), connect(N * 2, i * 2);
	}

	bool postcompute() {
		for (int i = 0; i < N; i++) {
			edges[parents[i].e].cap = parents[i].up;
			edges[parents[i].e ^ 1].cap = parents[i].down;
		}
		feasible = true;
		for (int i = 0; i < N; i++) {
			if (dss[i] >= 0) {
				if (edges[M + i * 2 + 1].cap) feasible = false;
			} else {
				if (edges[M + i * 2].cap) feasible = false;
			}
		}
		if (!feasible) return false;
		total_cost = 0;
		flows.clear();
		for (int i = 0; i < M; i += 2) {
			flows.push_back(lowers[i / 2] + edges[i ^ 1].cap);
			total_cost += flows.back() * edges[i].cost;
		}
		pots.pop_back();
		return true;
	}

	void push_flow(int ei0) {
		int u0 = edges[ei0 ^ 1].to, v0 = edges[ei0].to, del_u = v0;
		FLOW flow = edges[ei0].cap;
		COST clen = edges[ei0].cost + pots[u0] - pots[v0];
		bool del_u_side = true;
		int lca = get_lca(u0, v0, flow, del_u_side, del_u);
		if (flow) {
			int u = u0, v = v0;
			while (u != lca)
				parents[u].up += flow, parents[u].down -= flow,
					u = parents[u].p;
			while (v != lca)
				parents[v].up -= flow, parents[v].down += flow,
					v = parents[v].p;
		}
		int u = u0, par = v0;
		auto p_caps =
			make_pair(edges[ei0].cap - flow, edges[ei0 ^ 1].cap + flow);
		COST p_diff = -clen;
		if (!del_u_side) {
			swap(u, par);
			swap(p_caps.first, p_caps.second);
			p_diff *= -1;
		}
		int par_e = ei0 ^ (del_u_side ? 0 : 1);
		while (par != del_u) {
			int d = depth[par], idx = u * 2;
			while (idx != u * 2 + 1) {
				if (idx % 2 == 0)
					d++, pots[idx / 2] += p_diff, depth[idx / 2] = d;
				else d--;
				idx = nex[idx];
			}
			connect(pre[u * 2], nex[u * 2 + 1]);
			connect(u * 2 + 1, nex[par * 2]);
			connect(par * 2, u * 2);
			swap(parents[u].e, par_e);
			par_e ^= 1;
			swap(parents[u].up, p_caps.first);
			swap(parents[u].down, p_caps.second);
			swap(p_caps.first, p_caps.second);
			int next_u = parents[u].p;
			parents[u].p = par;
			par = u;
			u = next_u;
		}
		edges[par_e].cap = p_caps.first;
		edges[par_e ^ 1].cap = p_caps.second;
	}

	bool minor() {
		if (candidates.empty()) return false;
		COST best = 0;
		int best_ei = -1;
		int i = 0;
		while (i < int(candidates.size())) {
			int ei = candidates[i];
			if (!edges[ei].cap) {
				swap(candidates[i], candidates.back());
				candidates.pop_back();
				continue;
			}
			COST clen =
				edges[ei].cost + pots[edges[ei ^ 1].to] - pots[edges[ei].to];
			if (clen >= 0) {
				swap(candidates[i], candidates.back());
				candidates.pop_back();
				continue;
			}
			if (clen < best) best = clen, best_ei = ei;
			i++;
		}
		if (best_ei == -1) return false;
		push_flow(best_ei);
		return true;
	}

	int get_lca(int u, int v, FLOW& flow, bool& del_u_side, int& del_u) {
		auto up_u = [&]() {
			if (parents[u].down < flow)
				flow = parents[u].down, del_u = u, del_u_side = true;
			u = parents[u].p;
		};
		auto up_v = [&]() {
			if (parents[v].up <= flow)
				flow = parents[v].up, del_u = v, del_u_side = false;
			v = parents[v].p;
		};
		if (depth[u] >= depth[v]) {
			int num = depth[u] - depth[v];
			for (int i = 0; i < num; i++) up_u();
		} else {
			int num = depth[v] - depth[u];
			for (int i = 0; i < num; i++) up_v();
		}
		while (u != v) up_u(), up_v();
		return u;
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	NetworkSimplex<ll, ll> g(n * m + n + 1);
	int st = n * m + n;
	vector<vector<int>> a(m, vector<int>(n));
	rep(i, 0, n) rep(j, 0, m) cin >> a[j][i];
	rep(i, 0, n / 2) {
		g.add_edge(st, n * m + i, 0, 1, 0);
	}
	rep(i, n / 2, n) {
		g.add_edge(n * m + i, st, 0, 1, 0);
	}
	rep(i, 0, m) {
		rep(j, 0, n - 1) {
			g.add_edge(i * n + j, i * n + j + 1, 0, n, a[i][j] - a[i][j + 1]);
		}
		rep(j, 0, n) {
			g.add_edge(n * m + j, i * n + j, 0, 1, 0);
			g.add_edge(i * n + j, n * m + j, 0, 1, 0);
		}
	}
	auto [f, res] = g.solve();
	assert(f);
	cout << -res << '\n';
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0