結果

問題 No.957 植林
ユーザー wafrelkawafrelka
提出日時 2019-12-20 01:27:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,915 bytes
コンパイル時間 1,044 ms
コンパイル使用メモリ 100,724 KB
実行使用メモリ 24,960 KB
最終ジャッジ日時 2024-07-07 02:22:33
合計ジャッジ時間 6,091 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,752 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 113 ms
17,948 KB
testcase_04 AC 98 ms
16,964 KB
testcase_05 AC 98 ms
18,544 KB
testcase_06 AC 110 ms
19,284 KB
testcase_07 AC 109 ms
17,484 KB
testcase_08 AC 70 ms
18,116 KB
testcase_09 AC 69 ms
18,276 KB
testcase_10 AC 77 ms
18,980 KB
testcase_11 AC 69 ms
18,308 KB
testcase_12 AC 77 ms
18,176 KB
testcase_13 AC 60 ms
16,072 KB
testcase_14 AC 74 ms
19,492 KB
testcase_15 AC 65 ms
17,944 KB
testcase_16 AC 59 ms
15,852 KB
testcase_17 AC 67 ms
17,172 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void add_edge(graph&, int, int, i64)':
main.cpp:133:42: warning: narrowing conversion of '(&(& g)->std::vector<std::vector<edge> >::operator[](((std::vector<std::vector<edge> >::size_type)to)))->std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  133 |         g[from].push_back({to, g[to].size(), cap});
      |                                ~~~~~~~~~~^~
main.cpp:134:47: warning: narrowing conversion of '((&(& g)->std::vector<std::vector<edge> >::operator[](((std::vector<std::vector<edge> >::size_type)from)))->std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  134 |         g[to].push_back({from, g[from].size() - 1, 0});
      |                                ~~~~~~~~~~~~~~~^~~

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;

/* debug macros */
#ifdef WAFDAYO
#define DBG_PRINT(s, t, u) { std::cerr << s << " \e[2m=\e[m \e[1m" << t << "\e[m" << u; }
#else
#define DBG_PRINT(s, t, u) {}
#endif
#define dbg(x) DBG_PRINT(#x, x, std::endl)
#define dbgc(x) DBG_PRINT(#x, x, ", ")
#define idbg(x, i) DBG_PRINT(#x "[" << i << "]", x[i], std::endl)
#define idbgc(x, i) DBG_PRINT(#x "[" << i << "]", x[i], ", ")

/* IO utilities */
struct read_item { read_item() {}; template<class T> operator T() { T t; std::cin >> t; return t; } };

/* types and constants */
typedef long long i64;
const i64 inf = (i64)1.05e18;
// const int inf = (int)1.05e9;

/* Dinic Algorithm for Maximum Flow */
/* generic case: O( E V^2 ) */
/* network with unit capacities: O( min{E V^(2/3), E^(3/2)} ) */
/* network with each vertex (except for s, t)
    having a single (entering or outgoing) edge of capacity 1: O( E sqrt(V) ) */

struct edge { int to, rev; i64 cap; };
typedef vector<edge> vertex;
typedef vector<vertex> graph;

void compute_level(int s, vector<int>& level, graph& g)
{
	level.resize(g.size());
	fill(level.begin(), level.end(), -1);

	queue<int> q;
	level[s] = 0;
	q.push(s);

	while(!q.empty()) {

		const int v = q.front();
		q.pop();

		for(const auto& e : g[v]) {

			const int w = e.to;
			const i64 c = e.cap;

			if(c <= 0 || level[w] != -1)
				continue;
			level[w] = level[v] + 1;
			q.push(w);
		}
	}
}

i64 compute_flow_path(int v, int t, i64 f, vector<int>& iter, vector<int>& level, graph& g)
{
	if(v == t)
		return f;

	for(int& i = iter[v]; i < (int)g[v].size(); ++i) {

		auto& e = g[v][i];
		const i64 c = e.cap;
		const int w = e.to;

		if(c <= 0 || level[v] >= level[w])
			continue;

		const i64 d = compute_flow_path(w, t, min(f, c), iter, level, g);
		if(d <= 0)
			continue;
		e.cap -= d;
		g[w][e.rev].cap += d;
		return d;
	}

	return 0;
}

i64 max_flow(int s, int t, graph& g)
{
	i64 flow = 0;
	vector<int> level(g.size());
	vector<int> iter(g.size());

	while(true) {

		compute_level(s, level, g);
		if(level[t] == -1)
			break;
		fill(iter.begin(), iter.end(), 0);
		while(true) {
			const i64 f = compute_flow_path(s, t, inf, iter, level, g);
			flow += f;
			if(f <= 0)
				break;
		}
	}

	return flow;
}

void add_edge(graph& g, int from, int to, i64 cap) {
	g[from].push_back({to, g[to].size(), cap});
	g[to].push_back({from, g[from].size() - 1, 0});
}

int main() {

	const int h = read_item();
	const int w = read_item();
	vector<vector<i64>> gs(h);
	for(auto& v : gs) {
		v.resize(w);
	}
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			gs[i][j] = read_item();
		}
	}
	vector<i64> rs(h), cs(w);
	for(int i = 0; i < h; i++) {
		rs[i] = read_item();
	}
	for(int i = 0; i < w; i++) {
		cs[i] = read_item();
	}

	graph g(2 + h * w + w + h);
	const int left = 2;
	const int right = 2 + w + h;

	for(int i = 0; i < w; i++) {
		add_edge(g, 0, left + i, cs[i]);
		for(int j = 0; j < h; j++) {
			add_edge(g, left + i, right + i * h + j, inf);
		}
	}
	for(int i = 0; i < h; i++) {
		add_edge(g, 0, left + w + i, rs[i]);
		for(int j = 0; j < w; j++) {
			add_edge(g, left + w + i, right + j * h + i, inf);
		}
	}
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			add_edge(g, right + j * h + i, 1, gs[i][j]);
		}
	}

	i64 f = max_flow(0, 1, g);
	i64 ans = 0;
	for(int i = 0; i < h; i++) {
		ans += rs[i];
	}
	for(int i = 0; i < w; i++) {
		ans += cs[i];
	}
	ans -= f;

	printf("%lld\n", ans);

	return 0;
}

/* wafdayo~~~ */
0