模板类

用于考试复习吧

并查集(修改于18.11.7)

 1 int fa[100];
 2 void init()
 3 {
 4     for(int i=1;i<=n;++i) fa[i]=i;
 5 }
 6 int Myfind(int x)
 7 {
 8     if(x!=fa[x]) fa[x]=Myfind(fa[x]);
 9     return fa[x];
10 }
11 void Myunion(int x,int y){fa[Myfind(x)]=Myfind(y);}
12 bool Mycheck(int x,int y)
13 {
14     if(Myfind(x)==Myfind(y)) return true;
15     return false;
16 }

View Code

快速幂(修改于18.11.7)

 1 int Mypower(int x,int m)
 2 {
 3     int re=1;
 4     while(m)
 5     {
 6         if(m&1) re*=x,re%=p;
 7         x*=x,re%=p;
 8         m>>=1;
 9     }
10     return re;
11 }

View Code

最小生成树(修改于18.11.7)

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int fa[5005];
 5 struct edge{
 6     int s,t,l;
 7     bool operator < (const edge w) const{
 8         return l<w.l;
 9     }
10 }e[200005];
11 int n,m;
12 int Myfind(int x)
13 {
14     if(x!=fa[x]) fa[x]=Myfind(fa[x]);
15     return fa[x];
16 }
17 void Myunion(int x,int y)
18 {fa[Myfind(x)]=Myfind(y);}
19 bool Mycheck(int x,int y)
20 {
21     if(Myfind(x)==Myfind(y)) return true;
22     return false;
23 }
24 void Kruskal()
25 {
26     sort(e+1,e+1+m);
27     for(int i=1;i<=n;i++) fa[i]=i;
28     int nn=0,num=0;
29     for(int i=1;i<=m;i++)
30     {
31         if(nn==n-1) {printf("%d",num);return;}
32         if(!Mycheck(e[i].s,e[i].t)) 
33             Myunion(e[i].s,e[i].t),nn++,num+=e[i].l;
34     }
35     printf("orz");return;
36 }
37 int main()
38 {
39     scanf("%d%d",&n,&m);
40     for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].l);
41     Kruskal();
42     return 0;
43 }

Kruskal