結果

問題 No.957 植林
ユーザー nanophoto12
提出日時 2021-03-03 00:37:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,973 bytes
コンパイル時間 4,610 ms
コンパイル使用メモリ 264,608 KB
最終ジャッジ日時 2025-01-19 09:39:10
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 1 TLE * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

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

template<typename T>
void chmax(T& reference, T value) {
	reference = max(reference, value);
}

template<typename T>
void chmaxmap(map<T, T>& m, T key, T value) {
	if (m.count(key)) {
		chmax(m[key], value);
	}
	else {
		m[key] = value;
	}
}

template<typename T>
void chmin(T& reference, T value) {
	reference = min(reference, value);
}


#include <atcoder/all>
using namespace atcoder;

struct MaxFlowCalculator {
	typedef ll flow_type;
	//g.first...cost
	//g.second..dest
	int max_flow(int s, int t, const vector<vector<pair<flow_type, flow_type>>>& g) {
		struct edge_ { flow_type to, cap, rev; };
		vector<bool> used(g.size(), false);
		vector<vector<edge_>> G(g.size());
		for (int i = 0; i < g.size(); i++) for (int j = 0; j < g[i].size(); j++)
		{
			int from = i, to = g[i][j].second;
			flow_type cap = g[i][j].first;
			G[from].push_back({ to, cap, (flow_type)G[to].size() });
			G[to].push_back({ from, 0, (flow_type)G[from].size() - 1 });
		}
		auto dfs = [&](auto&& f, flow_type v, flow_type t, flow_type fl)->int {
			if (v == t) return fl;
			used[v] = true;
			rep(i, G[v].size()) {
				edge_& e = G[v][i];
				if (!used[e.to] && e.cap > 0) {
					flow_type d = f(f, e.to, t, min(fl, e.cap));
					if (d > 0) {
						e.cap -= d;
						G[e.to][e.rev].cap += d;
						return d;
					}
				}
			}
			return 0;
		};
		flow_type flow = 0;
		while (1) {
			used.assign(used.size(), false);
			flow_type f = dfs(dfs, s, t, INT_MAX);
			if (f == 0) return flow;
			flow += f;
		}
	}
};


int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<ll>> grid(h, vector<ll>(w));
	rep(y, h) {
		rep(x, w){
			cin >> grid[y][x];
		}
	}
	vector<ll> rows(h), cols(w);
	rep(i, h) cin >> rows[i];
	rep(i, w) cin >> cols[i];
	vector < vector<pair<ll, ll>>> graph(h*w + h*2 + w * 2 + 2);
	const int start = h * w + h * 2 + w * 2;
	const int goal = start + 1;
	const int rs = h * w;
	const int cs = h * w + 2 * h;
	rep(y, h) {
		rep(x, w) {
			int id = y * w + x;
			graph[start].emplace_back(grid[y][x], id);
			int xline = cs + x * 2;
			int yline = rs + y * 2;
			graph[id].emplace_back(1e16, xline);
			graph[id].emplace_back(1e16, yline);
		}
	}
	rep(y, h) {
		int yline = rs + y * 2;
		graph[yline].emplace_back(rows[y], yline + 1);
		graph[yline+1].emplace_back(1e16, goal);
	}
	rep(x, w) {
		int xline = cs + x * 2;
		graph[xline].emplace_back(cols[x], xline + 1);
		graph[xline + 1].emplace_back(1e16, goal);
	}
	ll sum = 0;
	rep(y, h) {
		sum += rows[y];
	}
	rep(x, w) {
		sum += cols[x];
	}
	MaxFlowCalculator f;
	auto a = f.max_flow(start, goal, graph);
	cout << sum - a << endl;
	return 0;
}
0