1795 . 咕嚕咕嚕呱啦呱啦
TopCoder
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
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
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 |