問題一覧 > 通常問題

No.330 Eigenvalue Decomposition

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 : 🐬hec🐬hec
6 ProblemId : 778 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-12-22 02:58:43

問題文

N×Nの正方対称行列Aがあり, M個の組$(a_{k},b_{k},c_{k}) $が与えられる.
非対角成分$A_{i,j} (i \ne j)$は$A_{a_{k},b_{k}}=A_{b_{k},a_{k}}=c_{k}$,そうでなければ$0$となる.
対角成分は$A_{i,i}$は$ \sum_{j=1}^N{A_{i,j}} = 0$を満たすように決める.
行列AのN個の固有値のうち0の個数を求めてください.

入力

$
N \ M \\
a_{1} \ b_{1} \ c_{1} \\
a_{2} \ b_{2} \ c_{2}\\
⋮ \\
a_{M} \ b_{M} \ c_{M}
$

1行目に2つの整数NとMが空白区切りで与えられる.
$M \ne 0$の場合,2行目からM+1行目に3つの整数$a_{i},b_{i},c_{i}$が空白区切りで与えられる.

入力は以下の制約を満たす.
$1 \le N \le 10^5$
$0 \le M \le \min( \frac{N(N-1)}{2},2 \times 10^5)$
$1 \le a_{i} < b_{i} \le N$
$1 \le c_{i} \le 10^9$
$(a_{i},b_{i}) \ne (a_{j},b_{j})$ $(i \ne j) $

出力

行列Aの固有値の0の数を1行に出力してください.

サンプル

サンプル1
入力
2 1
1 2 1
出力
1

この入力で与えられる行列Aは以下のとおりである.
$ A = \left(
\begin{array}{ccc}
-1 & 1 \\
1 & -1
\end{array}
\right)\\ $
行列Aの固有値は$\lambda=0 ,-2$ より,答えは1である.

サンプル2
入力
3 2
1 2 2 
2 3 1
出力
1

行列Aの固有値は$\lambda=0 ,\sqrt{3}-3,-3-\sqrt{3}$ より,答えは1である.

サンプル3
入力
4 2
1 2 5
3 4 6
出力
2

サンプル4
入力
10 9
1 2 3
4 7 11
2 3 5
3 9 12
2 10 12
1 9 10
5 6 11
7 8 15
1 10 11
出力
3

サンプル5
入力
330 0
出力
330

$M=0$のケースも存在する.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。