No.330 Eigenvalue Decomposition
タグ : / 解いたユーザー数 47
作問者 :
🐬hec
Problem Statement
There is an N×N square symmetric matrix A, and M tuples $(a_{k},b_{k},c_{k}) $ are given.
The off-diagonal entries $A_{i,j} (i \ne j)$ are given by $A_{a_{k},b_{k}}=A_{b_{k},a_{k}}=c_{k}$, and are $0$ otherwise.
The diagonal entries $A_{i,i}$ are determined so that $ \sum_{j=1}^N{A_{i,j}} = 0$ holds.
Find how many of the N eigenvalues of the matrix A are 0.
Input
$
N \ M \\
a_{1} \ b_{1} \ c_{1} \\
a_{2} \ b_{2} \ c_{2}\\
⋮ \\
a_{M} \ b_{M} \ c_{M}
$
The first line contains two integers N and M separated by a space.
If $M \ne 0$, each of lines 2 through M+1 contains three integers $a_{i},b_{i},c_{i}$ separated by spaces.
The input satisfies the following constraints.
$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) $
Output
Output on one line the number of eigenvalues of the matrix A that are 0.
Sample
Sample 1
Input
2 1 1 2 1
Output
1
The matrix A given by this input is as follows.
$ A = \left(
\begin{array}{ccc}
-1 & 1 \\
1 & -1
\end{array}
\right)\\ $
The eigenvalues of the matrix A are $\lambda=0 ,-2$, so the answer is 1.
Sample 2
Input
3 2 1 2 2 2 3 1
Output
1
The eigenvalues of the matrix A are $\lambda=0 ,\sqrt{3}-3,-3-\sqrt{3}$, so the answer is 1.
Sample 3
Input
4 2 1 2 5 3 4 6
Output
2
Sample 4
Input
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
Output
3
Sample 5
Input
330 0
Output
330
There are also cases with $M=0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。