TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

98.3% (174/177)

Submission's AC Ratio

49.9% (248/497)

Tags

Description

你,もも,逃出了棋盤格,朝著他的目標向前邁進,接下來的故事請自行想像,現在你在考建中資訊校內賽。
給你一張$n$個點$m$條邊的無向簡單圖$G$,每條邊的邊權非$0$即$1$。
再給你一個正整數$k$,問$G$是否存在一個生成樹其邊權總合為$k$。

Input Format

第一行有3個正整數$n, m, k$,分別代表$G$的點數、邊數以及題目要問的那個$k$。
接下來有$ m$行,每一行包含三個整數$u, v, c$,代表$G$裡存在一條邊權為$c$從$u$連到$v$的邊。

子題1滿足 : 若權重為$k$的生成樹存在,則不存在任何權重比$k$小的生成樹
子題2滿足 : 若權重為$k$的生成樹存在,則不存在任何權重比$k$大的生成樹

所有子題滿足:
$2 \leq n \leq 100000$
$2 \leq m \leq 300000$
$0 \leq k \leq n-1$
$1 \leq u, v \leq n$
$c \in {0, 1}$

Output Format

如果存在要求的生成樹,輸出"TAK"(不含引號),不然則輸出"NIE"(不含引號)。

Sample Input 1

#1:
3 3 1
1 2 1
2 3 0
1 3 0

#2:
4 3 2
1 2 1
2 3 1
3 4 1

Sample Output 1

#1:
TAK

#2:
NIE

Hints

我們說$T$是$G$的生成樹若且唯若:
1.$T$是一棵樹
2.$V(G) = V(T)$
3.$\forall e(u, v) \in T, e(u, v) \in G$

where $V(G)$代表$G$的點集合,$e(u, v)$代表一條連接點$u$跟$v$的邊

Problem Source

Subtasks

No. Testdata Range Score
1 0~3 10
2 4~8 20
3 9~14 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 3000 131072 262144 1
2 3000 131072 262144 1
3 3000 131072 262144 1
4 5000 131072 262144 2
5 5000 131072 262144 2
6 5000 131072 262144 2
7 5000 131072 262144 2
8 5000 131072 262144 2
9 5000 131072 262144 3
10 5000 131072 262144 3
11 5000 131072 262144 3
12 5000 131072 262144 3
13 5000 131072 262144 3
14 5000 131072 262144 3