h901. 電橘子與電耗子 - 高中生程式解題系統

內容

在一個遙遠的世界，有很多耗子，這些耗子住在耗子島上。耗子島上長著一種奇特的樹叫做「木木木木卡樹」( $Linlinca Tree$ ，簡稱 $LCT$ )，而這些樹長著一種奇特的果實，叫做「電木木木木卡」( $Linlincaorz$ )，它的外型酷似橘子，於是當地的耗子也把他們稱作「電橘子」( $Orzange$ )。

如果把這些電橘子擠成汁，就可以得到「電橘子汁」，耗子在喝了「電橘子汁」之後，就會轉變成第二型態「電耗子」( $Penguin0rz7$ )，是每個耗子成長的必經過程。

只是就算耗子島上長了很多木木木木卡樹，一顆電橘子也要經過 $5386$ 道工法才可以被製成電橘子汁，如果單用手工製作是絕對不夠的。正當耗子們為此苦惱時，由數一數二聰明的耗子組成的團隊「木木木木卡實驗室」( $Linlinca Lab$ )，提出了一種解決辦法，那就是把電橘子轉化成濃縮汁，他們發現，如果直接將電橘子變成電橘子汁，那過程會是非常繁瑣的，但如果可以把電橘子特定的部分先變成濃縮汁，之後再把濃縮汁混合，那就可以得到新鮮的電橘子汁了，而且因為提取某些部分，再用機器加工，比直接手工製作還要簡單太多了，於是這種方法很快被耗子島採用。

有了快速產出電橘子汁的方法後，原本一年只能有一隻耗子變成電耗子，現在一天就能有一隻，於是一年有將近 $300$ 隻！而耗子又分成兩個品種，有「火耗子」與「企鵝耗子」，如果兩個品種的耗子都變成了第二型態的電耗子，那就可以透過融合機，將兩隻不同品種的耗子融合變成第三型態的「火企鵝電耗子」( $Firepenguinorz$ )。

火耗子有 $k$ 個特徵值 $a_{1} \sim a_{k}$ ，企鵝耗子有 $k$ 個特徵值 $b_{1} \sim b_{k}$ ，兩隻耗子融合的發電值為 $\sum_{i = 1}^{k} a_{i} \times b_{i}$ ，機器的耐電值 $X$ 若小於兩隻耗子融合的發電值，那機器就會覺得自己太弱，然後撐 $10$ 秒後就爆了。

現在有 $n$ 隻火耗子與 $n$ 隻企鵝耗子要融合 $n$ 次，變成 $n$ 隻火企鵝電耗子，每次融合時可以選擇一隻還沒融合的火耗子與一隻還沒融合的企鵝耗子去融合。給你他們的特徵值，請你幫耗子們找出機器的耐電值至少要是多少。

如果你成功幫助他們了，他們就會給你年輕人的耗子尾汁。

輸入說明

第一行有兩個正整數 $n, k$ ，代表要融合出 $n$ 隻火企鵝電耗子，和每隻耗子有 $k$ 種特徵值。

接下來 $n$ 行，每行有 $k$ 個正整數 $a_{i, 1} \sim a_{i, k}$ ，代表第 $i$ 隻火耗子的 $k$ 個特徵值。

接下來 $n$ 行，每行有 $k$ 個正整數 $b_{i, 1} \sim b_{i, k}$ ，代表第 $i$ 隻企鵝耗子的 $k$ 個特徵值。

$1 \leq n, k \leq 300$
$1 \leq a_{i, j}, b_{i, j} \leq 10^{6}$

輸出說明

輸出一個整數 $X$ ，代表融合機的耐電值至少要是多少才能順利將 $n$ 隻火耗子與 $n$ 隻企鵝耗子融合。

範例輸入 #1

範例輸出 #1

範例輸入 #2

1 10
14 18 5 17 3 4 4 13 10 1
8 18 5 10 1 8 13 11 14 1

範例輸出 #2

範例輸入 #3

範例輸出 #3

測資資訊：

記憶體限制： 80 MB
不公開測資點#0 (5%): 3.0s , <1M
不公開測資點#1 (10%): 3.0s , <1M
不公開測資點#2 (10%): 3.0s , <1M
不公開測資點#3 (10%): 3.0s , <1M
不公開測資點#4 (10%): 3.0s , <1M
不公開測資點#5 (11%): 3.0s , <1M
不公開測資點#6 (11%): 3.0s , <1M
不公開測資點#7 (11%): 3.0s , <1M
不公開測資點#8 (11%): 3.0s , <1M
不公開測資點#9 (11%): 3.0s , <10M

提示：

在範例一中，火耗子的特徵值為 ${12}, {13}, {10}, {18}, {6}$ ，企鵝耗子的特徵值為 ${6}, {18}, {13}, {8}, {1}$ ，五次融合的發電值可以是 $6 \times 18, 10 \times 13, 12 \times 8, 13 \times 6, 18 \times 1$ ，這時機器的耐電值只需要 $10 \times 13 = 130$ 。

在範例二中，火耗子的特徵值為 ${14, 18, 5, 17, 3, 4, 4, 13, 10, 1}$ ，企鵝耗子的特徵值為 ${8, 18, 5, 10, 1, 8, 13, 11, 14, 1}$ ，發電值為 $1002$ 。

--------------------------------------------------------------------------------

$5 % ： k = 1$

$95 % ：無特別限制$

標籤:

flow matching 二分圖匹配二分搜匈牙利算法圖論網路流

出處:

第六屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
30928	r1cky (hehe)	h901	Java 解題心得	415	2022-06-22 16:31