結果

問題 No.957 植林
コンテスト
ユーザー polylogK
提出日時 2019-12-19 23:18:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,611 bytes
コンパイル時間 1,981 ms
コンパイル使用メモリ 187,956 KB
実行使用メモリ 32,904 KB
最終ジャッジ日時 2024-07-07 02:05:11
合計ジャッジ時間 7,061 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T>
struct Dinic{
	struct edge{
		int to;
		T cap;
		int rev;
	};
	
	const T INF;
	std::vector<std::vector<edge>> g;
	std::vector<T> min_cost;
	std::vector<int> itr;
	
	Dinic(int n) : INF(std::numeric_limits<T>::max()){
		g.resize(n);
	}
	
	void add_edge(int from, int to, T cap){
		g[from].push_back(edge{to, cap, (int)g[to].size()});
		g[to].push_back(edge{from, 0, (int)g[from].size() - 1});
	}
	
	bool bfs(int s, int t){
		min_cost.assign(g.size(), -1);
		std::queue<int> qu; qu.push(s); min_cost[s] = 0;
		
		while(!qu.empty()){
			auto p = qu.front(); qu.pop();
			
			for(auto e:g[p]){
				if(e.cap <= 0 or min_cost[e.to] != -1) continue;
				min_cost[e.to] = min_cost[p] + 1;
				qu.push(e.to);
			}
		}
		
		return min_cost[t] != -1;
	}
	
	T dfs(int idx, const int t, T flow){
		if(idx == t) return flow;
		for(int &i = itr[idx]; i < g[idx].size(); i++){
			edge &e = g[idx][i];
			
			if(e.cap <= 0 or min_cost[idx] >= min_cost[e.to]) continue;
			T d = dfs(e.to, t, std::min(flow, e.cap));
			if(d > 0){
				e.cap -= d;
				g[e.to][e.rev].cap += d;
				return d;
			}
			
		}
		
		return 0;
	}
	
	T max_flow(int s, int t){
		T flow = 0;
		while(bfs(s, t)){
			itr.assign(g.size(), 0);
			T f = 0;
			while((f = dfs(s, t, INF)) > 0) flow += f;
		}

		return flow;
	}
};

int main() {
	int h, w; scanf("%d%d", &h, &w); auto g = make_v<i64>(h, w);
	for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) scanf("%lld", &g[i][j]);
	std::vector<int> a(h), b(w);
	for(int i = 0; i < h; i++) scanf("%d", &a[i]);
	for(int i = 0; i < w; i++) scanf("%d", &b[i]);

	Dinic<i64> dinic(2 * h * w + 10);
	const int S = 2 * h * w + 1, T = 2 * h * w + 2;
	for(int i = 0; i < h; i++) {
		dinic.add_edge(S, i, 0);
		dinic.add_edge(i, T, a[i]);
	}
	for(int i = 0; i < w; i++) {
		dinic.add_edge(S, i + h, 0);
		dinic.add_edge(i + h, T, b[i]);
	}

	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			const int W = h + w + i * h + j;
			dinic.add_edge(S, W, g[i][j]);
			dinic.add_edge(W, i, g[i][j]);
			dinic.add_edge(W, j + h, g[i][j]);
		}
	}

	i64 ans = -dinic.max_flow(S, T);
	for(int i = 0; i < h; i++) ans += a[i];
	for(int i = 0; i < w; i++) ans += b[i];
	printf("%lld\n", ans);
	return 0;
}
0