結果

問題 No.1479 Matrix Eraser
ユーザー さかぽんさかぽん
提出日時 2021-05-14 22:30:09
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,341 bytes
コンパイル時間 995 ms
コンパイル使用メモリ 118,000 KB
実行使用メモリ 174,572 KB
最終ジャッジ日時 2024-04-10 01:02:14
合計ジャッジ時間 10,770 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
35,448 KB
testcase_01 AC 38 ms
26,592 KB
testcase_02 AC 38 ms
26,760 KB
testcase_03 AC 38 ms
26,336 KB
testcase_04 AC 38 ms
26,544 KB
testcase_05 AC 39 ms
26,464 KB
testcase_06 AC 37 ms
26,372 KB
testcase_07 AC 114 ms
52,180 KB
testcase_08 AC 205 ms
64,808 KB
testcase_09 AC 593 ms
103,716 KB
testcase_10 AC 1,816 ms
174,572 KB
testcase_11 AC 782 ms
115,632 KB
testcase_12 AC 147 ms
59,208 KB
testcase_13 AC 203 ms
66,312 KB
testcase_14 AC 156 ms
63,640 KB
testcase_15 AC 58 ms
39,004 KB
testcase_16 AC 173 ms
63,204 KB
testcase_17 TLE -
testcase_18 -- -
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 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

class D
{
	static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
	static (int, int) Read2() { var a = Read(); return (a[0], a[1]); }
	static void Main()
	{
		var (h, w) = Read2();
		var a = Array.ConvertAll(new bool[h], _ => Read());

		var sv = h + w;
		var ev = sv + 1;

		var rs = Enumerable.Range(0, h).Select(i => new[] { sv, i, 1L }).ToArray();
		var cs = Enumerable.Range(0, w).Select(j => new[] { h + j, ev, 1L }).ToArray();

		var d = new Dictionary<int, List<long[]>>();
		var dr = new Dictionary<int, HashSet<int>>();
		var dc = new Dictionary<int, HashSet<int>>();

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				var k = a[i][j];
				if (k == 0) continue;

				if (!d.ContainsKey(k))
				{
					d[k] = new List<long[]>();
					dr[k] = new HashSet<int>();
					dc[k] = new HashSet<int>();
				}

				d[k].Add(new[] { i, h + j, 1L });
				dr[k].Add(i);
				dc[k].Add(j);
			}
		}

		var r = 0L;

		foreach (var (k, es) in d)
		{
			if (es.Count == 1)
			{
				r++;
				continue;
			}

			foreach (var i in dr[k])
			{
				es.Add(rs[i]);
			}
			foreach (var j in dc[k])
			{
				es.Add(cs[j]);
			}

			r += MaxFlow(ev, sv, ev, es.ToArray());
		}
		Console.WriteLine(r);
	}

	static long MaxFlow(int n, int sv, int ev, long[][] dg)
	{
		var map = Array.ConvertAll(new int[n + 1], _ => new List<long[]>());
		foreach (var e in dg)
		{
			map[e[0]].Add(new[] { e[0], e[1], e[2], map[e[1]].Count });
			map[e[1]].Add(new[] { e[1], e[0], 0, map[e[0]].Count - 1 });
		}

		long M = 0, t;
		while ((t = Bfs(n, sv, ev, map)) > 0) M += t;
		return M;
	}

	static long Bfs(int n, int sv, int ev, List<long[]>[] map)
	{
		var from = new long[n + 1][];
		var minFlow = Enumerable.Repeat(long.MaxValue, n + 1).ToArray();
		var q = new Queue<long>();
		q.Enqueue(sv);

		while (q.Any())
		{
			var v = q.Dequeue();
			if (v == ev) break;
			foreach (var e in map[v])
			{
				if (from[e[1]] != null || e[2] == 0) continue;
				from[e[1]] = e;
				minFlow[e[1]] = Math.Min(minFlow[v], e[2]);
				q.Enqueue(e[1]);
			}
		}

		if (from[ev] == null) return 0;
		for (long v = ev; v != sv; v = from[v][0])
		{
			var e = from[v];
			e[2] -= minFlow[ev];
			map[e[1]][(int)e[3]][2] += minFlow[ev];
		}
		return minFlow[ev];
	}
}
0