結果

問題 No.957 植林
コンテスト
ユーザー lavox
提出日時 2021-07-28 20:55:29
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,080 bytes
コンパイル時間 3,124 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 98,856 KB
最終ジャッジ日時 2024-09-13 17:35:34
合計ジャッジ時間 25,287 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

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