该笔记是在大二时学习离散数学这门课程时做的,同时也看了其他有关的书,并用C++来验证这些定理。😄
素数-合数
设a , b a,b a , b 是两个整数,且b ≠ 0 b\ne 0 b = 0 。如果存在整数 c c c 使得 a = b c a=bc a = b c ,则称 a a a 被 b b b 整除 或者 b b b 整除 a a a ,记作 b ∣ a b\mid a b ∣ a ,不整除记作 b ∤ a b\nmid a b ∤ a
任何正整数都有两个正因子:1和它本身,称作它的平凡因子
,除了平凡因子外的因子称作 真因子
。
如果正整数 a a a 大于 1 且只能被1和它本身自己整除,则称 a a a 为素数
或质数
;如果 a a a 大于1且不是素数,则 a a a 为合数
。
a > 1 a>1 a > 1 是合数当且仅当 a = b c a=bc a = b c ,其中 1 < b < a , 1 < c < a 1<b<a,1<c<a 1 < b < a , 1 < c < a 。
算术基本定理
设 a > 1 a>1 a > 1 ,则
a = p 1 r 1 × p 2 r 2 × p 3 r 3 × . . . × p k r k a=p_1^{r_1}\times p_2^{r_2}\times p_3^{r_3}\times ... \times p_k^{r_k}
a = p 1 r 1 × p 2 r 2 × p 3 r 3 × . . . × p k r k
其中 p 1 , p 2 , . . . , p k p_1,p_2,...,p_k p 1 , p 2 , . . . , p k 是不同的素数,r 1 , r 2 , . . . r k r_1,r_2,...r_k r 1 , r 2 , . . . r k 是正整数 。定理中的表达式称作整数a a a 的 素因子分解
。比如
30 = 2 × 3 × 5 88 = 2 3 × 11 99099 = 3 2 × 7 × 1 1 2 × 13 1024 = 2 10 30=2\times 3\times 5\\
88=2^3\times 11\\
99099=3^2\times 7\times 11^2\times 13\\
1024=2^{10}
3 0 = 2 × 3 × 5 8 8 = 2 3 × 1 1 9 9 0 9 9 = 3 2 × 7 × 1 1 2 × 1 3 1 0 2 4 = 2 1 0
若所有的r i = 0 r_i=0 r i = 0 ,则 a = 1 a=1 a = 1 。显然,a a a 的素因子只能含有 a a a 中的素因子,即有下面推论:
推论:设 a = p 1 r 1 × p 2 r 2 × p 3 r 3 × . . . × p k r k a=p_1^{r_1}\times p_2^{r_2}\times p_3^{r_3}\times ... \times p_k^{r_k} a = p 1 r 1 × p 2 r 2 × p 3 r 3 × . . . × p k r k ,其中 p 1 , p 2 , . . . , p k p_1,p_2,...,p_k p 1 , p 2 , . . . , p k 是不同的素数,r 1 , r 2 , . . . r k r_1,r_2,...r_k r 1 , r 2 , . . . r k 是正整数 。
则正整数 d d d 为 a a a 的 因子 的充要条件是 d = p 1 s 1 × p 2 s 2 × . . . × p k s k d=p_1^{s_1}\times p_2^{s_2}\times ...\times p_k^{s_k} d = p 1 s 1 × p 2 s 2 × . . . × p k s k 。其中 0 ≤ s i ≤ r i , i = 1 , 2 , . . . , k 0\le s_i\le r_i,i=1,2,...,k 0 ≤ s i ≤ r i , i = 1 , 2 , . . . , k
例子:99099 99099 9 9 0 9 9 有多少个正因子 ?
解:由于 99099 = 3 2 × 7 × 1 1 2 × 13 99099=3^2\times 7\times 11^2\times 13 9 9 0 9 9 = 3 2 × 7 × 1 1 2 × 1 3 ,有推论可知, d = 3 s 1 × 7 s 2 × 1 1 s 3 × 1 3 s 4 d=3^{s_1}\times 7^{s_2}\times 11^{s_3}\times 13^{s_4} d = 3 s 1 × 7 s 2 × 1 1 s 3 × 1 3 s 4
s 1 ∈ [ 0 , 2 ] , s 2 ∈ [ 0 , 1 ] , s 3 ∈ [ 0 , 2 ] , s 4 ∈ [ 0 , 1 ] s_1\in [0,2],s_2\in [0,1],s_3\in [0,2],s_4\in [0,1] s 1 ∈ [ 0 , 2 ] , s 2 ∈ [ 0 , 1 ] , s 3 ∈ [ 0 , 2 ] , s 4 ∈ [ 0 , 1 ] ,因此 99099 99099 9 9 0 9 9 的正因子个数为 3 × 2 × 3 × 2 = 36 3\times 2\times 3\times 2=36 3 × 2 × 3 × 2 = 3 6 (排列组合)
素数定理
lim n → + ∞ π ( n ) n / ln n = 1 \lim_{n\to +\infty} \frac{\pi(n)}{n/\ln n}=1
n → + ∞ lim n / ln n π ( n ) = 1
检查一个正整数是否为素数称作 素数测试
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 typedef unsigned long long ull;const ull XX = 1e9 ;bool del[XX + 1 ];void eratosthene (ull NUM) { for (ull n = 2 ; n <= NUM; n++) if (!del[n]) for (ull i = n * n; i <= NUM; i += n) del[i] = true ; }int main () { ull n = 1000000000 ; eratosthene (n); for (int i = 2 ; i <= n; i++) if (!del[i]) cout << i << " " ; }
当 n n n 是合数时, 2 n − 1 2^n-1 2 n − 1 一定是合数
当 p p p 是素数时,称 2 p − 1 2^p-1 2 p − 1 的数为 梅森素数
。
线性筛
复杂度为 O ( n ) O(n) O ( n )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <iostream> #include <string.h> using namespace std;const int M=100001 ;int prime[M],isprime[M];int n,cnt;void fastprime () { memset (isprime,1 ,sizeof (isprime)); isprime[1 ]=0 ; for (int i=2 ;i<=n;i++){ if (isprime[i]) prime[cnt++]=i; for (int j=0 ;j<=cnt && i*prime[j]<=n;j++){ isprime[i*prime[j]]=0 ; if (i%prime[j]==0 )break ; } } }int main () { cin>>n; fastprime (); for (int i=0 ;i<cnt;i++) cout<<prime[i]<<" " ; cout<<endl; return 0 ; }
自然数分解为素数的乘积
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <iostream> #include <string.h> using namespace std;const int M=100001 ;int prime[M],isprime[M];int n,cnt;void fastprime () { memset (isprime,1 ,sizeof (isprime)); isprime[1 ]=0 ; for (int i=2 ;i<=n;i++){ if (isprime[i]) prime[cnt++]=i; for (int j=0 ;j<=cnt && i*prime[j]<=n;j++){ isprime[i*prime[j]]=0 ; if (i%prime[j]==0 )break ; } } }int main () { cin>>n; fastprime (); for (int i=0 ;i<cnt;i++){ while (n%prime[i]==0 ){ cout<<prime[i]<<" " ; n/=prime[i]; } } cout<<endl; return 0 ; }
同余
a与b模m同余 a ≡ b ( m o d m ) a\equiv b(\mod m) a ≡ b ( m o d m ) ,即: $a \mod m=b \mod m $
同余关系是等价关系
自反性. a ≡ ( a m o d m ) a\equiv (a\mod m) a ≡ ( a m o d m )
传递性. a ≡ b ( m o d m ) , b ≡ c ( m o d m ) ⇒ a ≡ c ( m o d m ) a\equiv b(\mod m),b\equiv c(\mod m)\Rightarrow a\equiv c(\mod m) a ≡ b ( m o d m ) , b ≡ c ( m o d m ) ⇒ a ≡ c ( m o d m )
对称性. a ≡ b ( m o d m ) ⇒ b ≡ a ( m o d m ) a\equiv b(\mod m)\Rightarrow b\equiv a(\mod m) a ≡ b ( m o d m ) ⇒ b ≡ a ( m o d m )
模算术运算。a ≡ b ( m o d m ) a\equiv b(\mod m) a ≡ b ( m o d m ) ,c ≡ d ( m o d m ) c\equiv d(\mod m) c ≡ d ( m o d m ) ,则
a ± c ≡ b ± d ( m o d m ) a × c ≡ b × d ( m o d m ) a k ≡ b k ( m o d m ) a\pm c\equiv b\pm d(\mod m)\\
a\times c\equiv b\times d(\mod m)\\
a^k\equiv b^k(\mod m)\\
a ± c ≡ b ± d ( m o d m ) a × c ≡ b × d ( m o d m ) a k ≡ b k ( m o d m )
设 c , m c,m c , m 互为素数,则 a ≡ b ( m o d m ) ⇔ c × a ≡ c × b ( m o d m ) a\equiv b(\mod m) \Leftrightarrow c\times a\equiv c\times b(\mod m) a ≡ b ( m o d m ) ⇔ c × a ≡ c × b ( m o d m )
欧拉定理和费马小定理
欧拉定理:设 a a a 和 n n n 互为素数,则 a f ( n ) ≡ 1 ( m o d n ) a^{f(n)}\equiv 1(\mod n) a f ( n ) ≡ 1 ( m o d n )
当 p p p 为素数时,f ( n ) = p − 1 f(n)=p-1 f ( n ) = p − 1 ,于是得到费马小定理
设 p p p 是素数,a a a 与 p p p 互素,则 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1(\mod p) a p − 1 ≡ 1 ( m o d p ) 或者另外一种形式 a p ≡ a ( m o d p ) a^p\equiv a(\mod p) a p ≡ a ( m o d p )
利用费马小定理,可以在不用因子分解的情况下就可以判断一个数是否为 合数 。比如 9 9 9 ,取 a = 2 a=2 a = 2 ,计算 2 9 − 1 ≡ 4 ( m o d 9 ) 2^{9-1}\equiv 4(\mod 9) 2 9 − 1 ≡ 4 ( m o d 9 ) ,对比费马小定理可知 9 是合数。
产生均匀伪随机数–线性同余法LCG
这种产生的随机数属于 统计学伪随机数生成器
产生伪随机数递推公式:
x n = ( a × x n − 1 + c ) m o d m , n = 1 , 2 , . . . x_n=(a\times x_{n-1}+c)\mod m ,n=1,2,...
x n = ( a × x n − 1 + c ) m o d m , n = 1 , 2 , . . .
其中 x 0 x_0 x 0 为初始时的种子数,若 c = 0 c=0 c = 0 ,上述递推式成为 乘同余数
。此时取 m = 2 31 − 1 , a = 7 5 , c = 0 m=2^{31}-1,a=7^5,c=0 m = 2 3 1 − 1 , a = 7 5 , c = 0 的乘同余法是最常用的均匀伪随机数发生器。a a a 还可以取其他数值 48271
#include <bits/stdc++.h> using namespace std;size_t __SEED=1 ;void my_srand (size_t S) { __SEED=S; }size_t my_rand () { int m=0x7fffffff ,c=0 ,a=16807 ; __SEED=(a*__SEED+c) % m; return __SEED; }int main () { my_srand (time (NULL )); for (int i=0 ;i<10 ;i++) cout<<my_rand ()<<endl; }
快速幂
二分思想–递归法
求 f ( a , b ) = a b f(a,b)=a^b f ( a , b ) = a b ,递归式如下:
a b = f ( a , b ) = { 1 , b = 0 a × f ( a , b − 1 ) , b 为 奇 数 f ( a b 2 , b 2 ) × f ( a b 2 , b 2 ) , b 为 偶 数 a^b=f(a,b)=
\begin{cases}
1&,b=0\\
a\times f(a,b-1)&,b为奇数\\
f(a^{\frac{b}{2}},\frac{b}{2})\times f(a^{\frac{b}{2}},\frac{b}{2})&,b为偶数\\
\end{cases}
a b = f ( a , b ) = ⎩ ⎪ ⎨ ⎪ ⎧ 1 a × f ( a , b − 1 ) f ( a 2 b , 2 b ) × f ( a 2 b , 2 b ) , b = 0 , b 为 奇 数 , b 为 偶 数
using ll=long double ;ll quick_pow (int a,int b) { if (b==0 )return 1 ; if (b&1 )return a*quick_pow (a,b-1 ); ll m=quick_pow (a,b/2 ); return m*m; }
二进制位分解–迭代法
a b a^b a b ,b b b 的二进制位(取其中有效的位: 1) 。指数的变化位 . . . 64 32 16 8 4 2 1 ... 64\quad 32\quad 16\quad 8\quad 4\quad 2\quad 1 . . . 6 4 3 2 1 6 8 4 2 1 ,每次翻倍
如 b = 13 = ( 1101 ) 2 = 2 3 + 2 2 + 2 0 = 8 + 4 + 1 b=13=(1101)_2=2^3+2^2+2^0=8+4+1 b = 1 3 = ( 1 1 0 1 ) 2 = 2 3 + 2 2 + 2 0 = 8 + 4 + 1
a 13 = a 8 + 4 + 1 = a 2 3 + 2 2 + 2 0 = a 8 × a 4 × a 1 a^{13}=a^{8+4+1}=a^{2^3+2^2+2^0}=a^8\times a^4\times a^1 a 1 3 = a 8 + 4 + 1 = a 2 3 + 2 2 + 2 0 = a 8 × a 4 × a 1
using ll=long double ;ll quick_pow (ll a,int b) { ll ans=1 ; while (b){ if (b&1 ) ans=ans*a; a=a*a; b>>=1 ; } return ans; }
快速幂-取模运算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <cstdio> #include <cstdlib> int b, p, k;typedef unsigned long long ll; unsigned long long qm () { if (p == 0 ) return 1 % k; ll ans = 1 , bb = b, pp = p; bb %= k; while (pp) { if (pp & 1 ) ans = (ans * bb) % k; bb = (bb * bb) % k; pp >>= 1 ; } return ans; }int main () { scanf ("%d%d%d" , &b, &p, &k); unsigned long long ans = qm (); printf ("%d^%d mod %d=%ld\n" , b, p, k, ans); return 0 ; }
欧拉函数
欧拉函数(Euler’s totient function),即 ϕ ( x ) \phi(x) ϕ ( x ) ,表示的是 小于等于 n n n 和 n n n 互质(公约数只有1) 的数的个数。
ϕ ( n ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) ( 1 − 1 p 3 ) ⋯ ( 1 − 1 p k ) \phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\cdots (1-\frac{1}{p_k})
ϕ ( n ) = n ( 1 − p 1 1 ) ( 1 − p 2 1 ) ( 1 − p 3 1 ) ⋯ ( 1 − p k 1 )
也可以写成
ϕ ( n ) = n p 1 − 1 p 1 p 2 − 1 p 2 ⋯ p k − 1 p k \phi(n)=n\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots\frac{p_k-1}{p_k}
ϕ ( n ) = n p 1 p 1 − 1 p 2 p 2 − 1 ⋯ p k p k − 1
其中 p 1 , p 2 , p k p_1,p_2,p_k p 1 , p 2 , p k 为分解出来的不同的 质因数。
求某个数的欧拉函数值如下,复杂度为 O ( n ) O(\sqrt{n}) O ( n )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <iostream> #include <cmath> using namespace std;int phi (int n) { int ans=n; int cnt=sqrt (n+0.5 )+1 ; for (int i=2 ;i<cnt;i++){ if (n%i==0 ){ ans-=ans/i; while (n%i==0 )n/=i; } if (n==1 )break ; } if (n>1 )ans-=ans/n; return ans; }int main () { int n; cin>>n; cout<<phi (n)<<endl; return 0 ; }
线性筛求欧拉函数表
复杂度为 O ( n ) O(n) O ( n )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <iostream> #include <cstring> using namespace std;const int N=100001 ;bool isprime[N];int prime[N];int phi[N];int cnt;void fastphi (int n) { memset (isprime,1 ,sizeof (isprime)); isprime[0 ]=isprime[1 ]=0 ; phi[1 ]=1 ; for (int i=2 ;i<=n;i++){ if (isprime[i]) { prime[cnt++]=i; phi[i]=i-1 ; } for (int j=0 ;j<=cnt && i*prime[j]<=n;j++){ isprime[i*prime[j]]=0 ; if (i%prime[j]==0 ) { phi[i*prime[j]]=phi[i] * prime[j]; break ; } phi[i*prime[j]]=phi[i] * (prime[j]-1 ); } } }int main () { int n; cin>>n; fastphi (n); for (int i=0 ;i<cnt;i++) cout<<phi[i]<<" " ; cout<<endl; return 0 ; }
霍纳规则
适用范围 :多项式求值问题
简介 :假设有 n + 2 n+2 n + 2 个实数 a 0 , a 1 , . . . , a n a_0,a_1,...,a_n a 0 , a 1 , . . . , a n 和 x x x 的序列,要对多项式 P n ( x ) = a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 P_n(x)= a_nx_n+a_{n-1}x_{n-1}+...+a_1x+a_0 P n ( x ) = a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 求值,直接方法是对每一项分别求值,并把每一项求的值累加起来,这种方法十分低效,它需要进行 n + ( n − 1 ) + . . . + 1 = n ( n + 1 ) / 2 n+(n-1)+...+1=n(n+1)/2 n + ( n − 1 ) + . . . + 1 = n ( n + 1 ) / 2 次乘法运算和 n n n 次加法运算。有没有更高效的算法呢?答案是肯定的。
通过如下变换我们可以得到一种非常快的算法,即 P n ( x ) = a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 = ( ( . . . ( ( ( a n x + a n − 1 ) x + a n − 2 ) x + a n − 3 ) . . . ) x + a 1 ) x + a 0 P_n(x)= a_nx_n+a_{n-1}x_{n-1}+...+a_1x+a_0=((...(((a_nx +a_{n-1})x+a_{n-2})x+ a_{n-3})...)x+a1)x+a0 P n ( x ) = a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 = ( ( . . . ( ( ( a n x + a n − 1 ) x + a n − 2 ) x + a n − 3 ) . . . ) x + a 1 ) x + a 0 ,这种求值的安排我们称为 霍纳法则 。
C++ code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> using namespace std;double horner_rule (double *A,int n,double x) { double ans=0 ; for (int i=n-1 ;i>=0 ;i--){ ans=ans*x+A[i]; } return ans; }int main () { double A[]={1 ,2 ,3 ,4 }; double x=2 ; cout<<horner_rule (A,sizeof (A)/sizeof (A[0 ]),x)<<endl; return 0 ; }
排列组合
( 1 ) P ( n , r ) = n ! ( n − r ) ! . n ≥ r ( 2 ) C ( n , r ) = n ! r ! ∗ ( n − r ) ! . n ≥ r (1)\ P(n,r) = \frac{n!}{(n-r)!}.n\ge r\\
(2)\ C(n,r) = \frac{n!}{r!*(n-r)!}.n\ge r\\
( 1 ) P ( n , r ) = ( n − r ) ! n ! . n ≥ r ( 2 ) C ( n , r ) = r ! ∗ ( n − r ) ! n ! . n ≥ r
推论: 设 n , r n,r n , r 为正整数,则
C ( n , r ) = n r C ( n − 1 , r − 1 ) C ( n , r ) = C ( n , n − r ) C ( n , r ) = C ( n − 1 , n − r ) + C ( n − 1 , r ) C(n,r)=\frac{n}{r}C(n-1,r-1)\\
C(n,r)=C(n,n-r)\\
C(n,r)=C(n-1,n-r)+C(n-1,r)
C ( n , r ) = r n C ( n − 1 , r − 1 ) C ( n , r ) = C ( n , n − r ) C ( n , r ) = C ( n − 1 , n − r ) + C ( n − 1 , r )
例1:从 S = { 1 , 2 , . . . , n } S=\{1,2,...,n\} S = { 1 , 2 , . . . , n } 中选择k k k 个不相邻的数,有多少种方法?
C ( n − ( k − 1 ) , k ) = C ( n − k + 1 , k ) C(n-(k-1),k)=C(n-k+1,k)
C ( n − ( k − 1 ) , k ) = C ( n − k + 1 , k )
图论
握手定理
∑ v ∈ V d e g ( v ) = 2 ∣ E ∣ \sum_{v\in V}deg(v)=2|E|
v ∈ V ∑ d e g ( v ) = 2 ∣ E ∣
在任何有向图 中,所有顶点的 入度 之和等于所有顶点的 出度 之和,等于边数 ∣ E ∣ |E| ∣ E ∣ 。
平面图
无向树-树
树:边 数 = 顶 点 数 − 1 ⇔ e = n − 1 边数=顶点数-1\Leftrightarrow e=n-1 边 数 = 顶 点 数 − 1 ⇔ e = n − 1
设 G G G 为 n n n 阶 m m m 条边的无向连通图,则 m ≥ n − 1 m\ge n-1 m ≥ n − 1
设有完全 m m m 叉树,其树叶数为 t t t ,分支点数(内点+树根)为 i i i ,则 ( m − 1 ) × i = t − 1 (m-1)\times i=t-1 ( m − 1 ) × i = t − 1
证明:m ∗ i = ( t + i ) − 1 m*i=(t+i)-1 m ∗ i = ( t + i ) − 1
设 G G G 是有 n n n 个结点,m m m 条边的连通图,必须删去 G G G 的 m − n + 1 m-n+1 m − n + 1 条边,才能确定 G G G 的一棵 生成树 。
最小的生成树
为了造出一棵最小生成树,我们从最小边权的边开始,按边权从小到大依次加入,如果某次加边产生了环,就扔掉这条边,直到加入了 n − 1 n-1 n − 1 条边,即形成了一棵树。
最小生成树一定是含有 n n n 个顶点和 n − 1 n-1 n − 1 条边。
所以可以得到一个推论:
n − 1 n-1 n − 1 条边 <=> 1 1 1 棵最小生成树
n − 2 n-2 n − 2 条边 <=> 2 2 2 棵最小生成树(将 n − 1 n-1 n − 1 分为 n − 1 n-1 n − 1 和1 1 1 条边)
n − 3 n-3 n − 3 条边 <=> 3 3 3 棵最小生成树
⋮ \vdots ⋮
n − k n-k n − k 条边 <=> k k k 棵最小生成树。其实可以这么理解:从 n-1 条边得到了一颗最小生成树之后,根据 树 的定义,我们知道,若从一颗最小生成树中删除 i i i 条边后,会形成多个树,也就是森林 ;而且每一个子树也是最小生成子树。
注意: 一个顶点也可与作为一颗最小生成树。比如洛谷有一题 p1195
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include <algorithm> #include <cstring> #include <iostream> #include <queue> using namespace std;#define INF 0x7fffffff #define N 100001 int n, m, k, cnt, ans;int f[N];struct edge { int u, v, w; }; vector<edge> E;struct cmp { bool operator () (edge e1, edge e2) { return e1.w < e2.w; } };int find (int x) { if (f[x] == x) return x; return f[x] = find (f[x]); }int find2 (int x) { while (f[x] != x) { f[x] = f[f[x]]; x = f[x]; } return f[x]; }void kruskal () { for (int i = 0 ; i < E.size (); i++) { edge e = E[i]; int f1 = find2 (e.u); int f2 = find2 (e.v); if (f1 == f2) continue ; f[f1] = f2; ans += E[i].w; cnt++; if (cnt >= n - k) break ; } if (cnt == n - k) cout << ans; else cout << "No Answer" ; }int main () { ios::sync_with_stdio (0 ); cin.tie (0 ); cin >> n >> m >> k; int u, v, w; for (int i = 1 ; i <= n; i++) f[i] = i; for (int i = 0 ; i < m; i++) { cin >> u >> v >> w; E.push_back (edge{u, v, w}); } sort (E.begin (), E.end (), cmp ()); kruskal (); return 0 ; }