結果

問題 No.957 植林
ユーザー lavoxlavox
提出日時 2021-07-28 20:55:29
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 3,080 bytes
コンパイル時間 3,007 ms
コンパイル使用メモリ 77,872 KB
実行使用メモリ 94,568 KB
最終ジャッジ日時 2023-10-11 18:42:26
合計ジャッジ時間 25,026 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 113 ms
44,804 KB
testcase_01 AC 111 ms
39,144 KB
testcase_02 AC 112 ms
39,752 KB
testcase_03 AC 1,124 ms
88,356 KB
testcase_04 AC 1,141 ms
86,328 KB
testcase_05 AC 1,050 ms
87,828 KB
testcase_06 AC 1,146 ms
94,568 KB
testcase_07 AC 1,095 ms
87,676 KB
testcase_08 AC 917 ms
88,224 KB
testcase_09 AC 879 ms
83,336 KB
testcase_10 AC 999 ms
91,440 KB
testcase_11 AC 971 ms
87,472 KB
testcase_12 AC 956 ms
89,076 KB
testcase_13 AC 728 ms
75,024 KB
testcase_14 AC 912 ms
86,460 KB
testcase_15 AC 878 ms
83,764 KB
testcase_16 AC 821 ms
84,704 KB
testcase_17 AC 813 ms
82,472 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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = Integer.parseInt(sc.next());
		int W = Integer.parseInt(sc.next());
		long[][] G = new long[H][W];
		for ( int h = 0 ; h < H ; h++ ) {
			for ( int w = 0 ; w < W ; w++ ) {
				G[h][w] = Long.parseLong(sc.next());
			}
		}
		long ans = 0;
		long[] R = new long[H];
		long[] C = new long[W];
		for ( int h = 0 ; h < H ; h++ ) {
			R[h] = Long.parseLong(sc.next());
			ans += R[h];
		}
		for ( int w = 0 ; w < W ; w++ ) {
			C[w] = Long.parseLong(sc.next());
			ans += C[w];
		}
		sc.close();

		DinicNetwork net = new DinicNetwork(H * W + H + W + 2);
		// 0
		// 1...H
		// H+1...H+W
		// H+W+1...H+W+H*W
		// H+W+H*W+1
		
		for ( int h = 0 ; h < H ; h++ ) {
			net.addEdge(0, h + 1, R[h]);
			for ( int w = 0 ; w < W ; w++ ) {
				net.addEdge(h + 1, H + W + h * W + w + 1, net.INF);
				net.addEdge(H + W + h * W + w + 1, H + W + H * W + 1, G[h][w]);
			}
		}
		for ( int w = 0 ; w < W ; w++ ) {
			net.addEdge(0, H + w + 1, C[w]);
			for ( int h = 0 ; h < H ; h++ ) {
				net.addEdge(H + w + 1, H + W + h * W + w + 1, net.INF);
			}
		}
		
		long max = net.maxFlow(0, H + W + H * W + 1);
		System.out.println(ans - max);
	}
}

class DinicNetwork {
	static final long INF = Long.MAX_VALUE;
	int[] level = null;
	int[] iter = null;
	ArrayList<Edge> edges[] = null;

	class Edge {
		int to = 0;
		long cap = 0;
		int rev = 0;
		Edge( int to, long cap, int rev ) {
			this.to = to;
			this.cap = cap;
			this.rev = rev;
		}
	}

	public DinicNetwork(int N) {
		level = new int[N];
		iter = new int[N];
		edges = new ArrayList[N];
		for ( int i = 0 ; i < N ; i++ ) {
			edges[i] = new ArrayList<>();
		}
	}

	public void addEdge(int from, int to, long cap) {
		edges[from].add(new Edge(to, cap, edges[to].size()));
		edges[to].add(new Edge(from, 0, edges[from].size() - 1));
	}

	private void bfs(int s) {
		Arrays.fill(level, -1);
		Deque<Integer> queue = new ArrayDeque<Integer>();
		level[s] = 0;
		queue.add(s);
		while ( !queue.isEmpty() ) {
			int v = queue.poll();
			for ( Edge e : edges[v] ) {
				if ( e.cap > 0 && level[e.to] < 0 ) {
					level[e.to]= level[v] + 1;
					queue.add(e.to);
				}
			}
		}
	}

	private long dfs(int v, int t, long f) {
		if ( v == t ) return f;
		while ( iter[v] < edges[v].size() ) {
			Edge e = edges[v].get(iter[v]);
			if ( e.cap > 0 && level[v] < level[e.to] ) {
				long d = dfs(e.to, t, Math.min(f, e.cap));
				if ( d > 0 ) {
					e.cap = add(e.cap, -d);
					edges[e.to].get(e.rev).cap = add(edges[e.to].get(e.rev).cap, d);
					return d;
				}
			}
			iter[v]++;
		}
		return 0;
	}

	private long add(long a, long diff) {
		return a == INF ? INF : a + diff;
	}

	public long maxFlow(int s, int t) {
		long flow = 0;
		while ( true ) {
			bfs(s);
			if ( level[t] < 0 ) return flow;
			Arrays.fill(iter, 0);
			long f = 0;
			while ( (f = dfs(s, t, INF)) > 0 ) {
				flow += f;
			}
		}
	}
}
0