a666: 瑞利散射
標籤 : 圖論
通過比率 : 5% (1 人 / 21 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-05-15 03:22

內容

你看過《瑞利散射》嗎?
這是一部熱血的機器人動畫,而我們今天要解的問題恰好和這部動畫有一些些關聯。

1972年的阿波羅17號登月計畫中,人類發現了古代的黑科技「超空間門(Hypergate)」。
然而,直到數百年後,人類才真正掌握了這項科技。
另一方面,在這百年間,由於人口的過度增長,人類開始向外尋找其他適合居住的行星。
目前,包含地球,共有 $n$ 顆行星是有人居住的。

為了節省往來各行星的交通時間,各行星領導人達成了一項協議:
每顆行星都應該建造一個雙向超空間門,通往另一顆行星(可以是自己)。
你的任務就是評估這 $n$ 個超空間門所帶來的效益。

為了簡單起見,設行星 $i$ 決定建造通往行星 $p_i$ 的雙向超空間門,而利用該超空間門的旅行時間是 $t_i$。
若一個旅行者先後利用了行星 $i_1, i_2, \ldots, i_k$ 建造的超空間門,旅行時間就是 $t_{i_1} + t_{i_2} + \ldots + t_{i_k}$。
現在給定 $K > 0$,請你計算有幾對行星,在只利用超空間門的情形下,旅行時間的最小值不超過 $K$。

輸入說明

第一行有一個正整數 $T$,代表總共有幾筆測試資料。
每筆測試資料的第一行有兩個正整數 $n, K$,分別代表有人類居住的行星數,與效益評估中的 $K$ 值。
接下來的 $n$ 行,第 $i$ 行有兩個正整數 $p_i, t_i$,代表行星 $i$ 建立了一個通往行星 $p_i$ 的雙向超空間門,旅行時間為 $t_i$。

  • $1 \leq T \leq 20$
  • $1 \leq n \leq 50000$
  • $1 \leq K \leq 10^6$
  • $1 \leq p_i \leq n$
  • $1 \leq t_i \leq 10^4$
輸出說明

對於每筆測試資料,請輸出一行一個整數,代表有幾對行星,在只利用超空間門的情形下,旅行時間的最小值不超過 $K$。

範例輸入
2
5 3
2 2
3 1
1 2
3 2
2 2
3 2
1 10
3 2
2 3
範例輸出
7
1
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (100%): 4.0s , <10M
提示 :

如果你不知道瑞利散射是什麼梗
請直接google「瑞利散射 動畫」

(2018-05-15 更新)
由於以前的測資沒有好好生 可能會讓一些 random 暴力解 AC
決定把這題的測資更新成和 IOI Camp 2017 Final 一樣
儘管輸入格式改了
我看了一下這題的 AC code 們後 發現除了自己以外沒有人寫出來
// 那些 AC 的 不是直接輸出答案 就是 copy-and-paste 我的 code
所以沒有讓本來該 AC 的人 WA 掉 可喜可賀(?

標籤:
圖論
出處:
IOIcamp2017 [編輯:
xavier13540 (柊 四千)
]


編號 身分 題目 主題 人氣 發表日期
14005
xavier13540 (柊 四千)
a666
作者提供的解法
83 2018-05-27 13:08