h988. 嗯呀喜歡這個
標籤 : Dijkstra 最短路徑 貪心
通過比率 : 2人/8人 ( 25% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-19 19:04

內容

計幾、哈哈與嗯呀是一家人,表面上很和善的三個人,卻有不為人知的祕密:計幾是計算幾何大師,他可以在 $O(1)$ 的時間求出 $48763$ 個凸包;哈哈是哈哈大師,她會走到路上對別人哈哈大笑;嗯呀有一個超能力,她可以看透別人的心,知道別人血管是如何分布的。

今天嗯呀在看電視時,有一個節目叫做「$\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠」,嗯呀用手指著電視跟計幾說:「嗯呀喜歡這個。」但是計幾說嗯呀還沒寫完她的中班微積分作業,寫完了才能看。嗯呀指著微積分課本,說:「嗯呀不喜歡這個。」

為了不寫微積分作業,嗯呀必須要讓計幾開心。有什麼東西能讓人開心呢?嗯呀想到了,可以給計幾吃糖果,計幾吃了糖果後嗯呀就可以執行她的計畫了:嗯呀的糖果可以活化計幾的血管,而計幾的血管系統有 $n$ 個節點,這 $n$ 個節點以 $m$ 條雙向的血管連接,並且一定可以互相到達。一個節點的快樂值 $v_i$ 為節點 $s$ 到達節點 $i$ 的最短路徑 ($v_s = 0$),嗯呀的糖果可以讓計幾血管系統的 $a$ 個節點感到快樂,而計幾的總快樂值就是這 $a$ 個節點的快樂值相加。嗯呀的糖果不只可以讓 $a$ 個節點感到快樂,她還可以使這 $a$ 個節點裡其中 $b$ 個節點產生「黑色衝動」:一個節點除了快樂值 $v_i$ 外,還有黑值 $d_i$ 與色值 $c_i$,經過「黑色衝動」後,一個節點的快樂值會從 $v_i$ 變成 $d_i\times v_i + c_i$。不管「黑色衝動」後的快樂值是變大還是變小,嗯呀都必須要讓 $a$ 個節點裡恰好 $b$ 個節點產生「黑色衝動」。

嗯呀想請問你:要如何選擇感到快樂的節點和從感到快樂的節點選擇產生「黑色衝動」的節點,才能使計幾的總快樂值最大。

輸入說明

第一行有兩個正整數 $n, m, a, b, s$,代表計幾的血管系統有幾個節點、有幾條雙向血管、有幾個節點感到快樂、感到快樂的節點裡有幾個會有「黑色衝動」,和節點 $s$。

第二行有 $n$ 個整數 $d_1 \sim d_n$,代表每個節點的黑值。

第三行有 $n$ 個整數 $c_1 \sim c_n$,代表每個節點的色值。

接下來 $m$ 行,每行有三個整數 $x, y, w$,代表節點 $x$ 和節點 $y$ 之間有一條連接他們、長度為 $w$ 的雙向血管,保證兩個節點最多只會有一條血管連接,並且不會有節點連接自己。

  • $2\leq n \leq 10^5$
  • $n - 1 \leq m \leq \min (2\times 10^5, \frac{n\times (n - 1)}{2})$
  • $0\leq b \leq a \leq n$
  • $-10^4 \leq d_i, c_i \leq 10^4$
  • $1\leq x, y,s \leq n$
  • $1\leq w\leq 10^4$
輸出說明

輸出一個整數代表嗯呀在適當的選擇快樂的節點後,計幾可以獲得的最大總快樂值 (有可能是負的)

範例輸入 #1
10 37 10 7 6
-4 9 -15 -72 -43 57 98 -10 4 4
78 -66 34 -17 -29 -29 -69 -14 -22 -37
6 10 5
9 4 10
3 10 1
5 1 26
7 10 6
8 3 15
5 6 17
3 4 18
2 10 22
8 9 17
9 2 15
10 8 4
6 8 17
1 3 30
2 8 16
7 5 8
9 5 15
1 10 11
3 5 16
3 9 14
7 9 7
1 9 14
6 9 18
5 8 3
4 2 10
4 1 21
4 10 4
6 2 16
7 3 10
10 9 3
8 4 5
7 4 29
5 10 22
7 6 17
2 3 27
4 5 9
1 8 12
範例輸出 #1
1039
測資資訊:
記憶體限制: 200 MB
不公開 測資點#0 (10%): 2.5s , <10M
不公開 測資點#1 (18%): 2.5s , <10M
不公開 測資點#2 (18%): 2.5s , <10M
不公開 測資點#3 (18%): 2.5s , <10M
不公開 測資點#4 (18%): 2.5s , <10M
不公開 測資點#5 (18%): 2.5s , <1K
提示 :

「對不起,嗯呀其實 $\dots$ 很想跟你當好朋友$\sim$」

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

$10\%:a = n$

$90\%:無特別限制$

標籤:
Dijkstra 最短路徑 貪心
出處:
第六屆簡單的小競賽 [管理者: becaido (Caido) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」