一、文件

  1. 文件名不要打错
  2. 保存关闭文件之后用命令行按规定指令编译
  3. 检查输入输出文件
  4. ⋆\color{red}\star 测试大样例之前用规定指令编译
  5. cerr 调试一定要删
  6. 关闭所有窗口

二、题目

  1. 必须计算空间复杂度
  2. ⋆\color{red}\star 注意溢出和越界
    -fsanitize=address,undefined
  3. 注意时间常数，进行极限数据测试
  4. 不确定的算法写完如果有时间要对拍
  5. 大模数必须复制，注意是否素数
  6. ⋆\color{red}\star 必须用scanf&prinf输入输出
  7. ceil()、floor()、pow()返回值是double的
  8. unordered_map、unordered_map更快

三、算法

  1. DP一定要计算空间
  2. ⋆\color{red}\star 线段树不要忘记pushup和pushdown
  3. 考前看一下模板
  4. ⋆\color{red}\star 没思路依次想这些方法：DP、贪心、二分答案、数学、图论、猜结论、先写暴力再优化
  5. 随机化可能有用
  6. 多种贪心、错解取最优
  7. ⋆\color{red}\star STL
    name func
    set insert,find,erase,size,empty,clear
    map [],auto x:a,count,erase
    stack pop,push,front,empty
    queue pop,push,front,empty
    deque push_back,push_front,pop...,insert,erase,[]
    priority_queue pop,push,top,empty

四、模板

GCD qpow inv Dijkstra SPFA Kruskal
  1. GCD
1
2
3
int gcd(int x,int y) {
    return y?gcd(y,x%y):x;
}
  1. qpow（nkn^k）
1
2
3
4
5
6
7
long long ans=1;
while(k){
    if(k&1)
        ans=ans*n%p;
    n=n*n%p;
    k>>=1;
}

  1. inv（⋆\color{red}\star 质数）

    inv(x)=xmod−2  (mod is a prime)\text{inv}(x)=x^{mod-2}\ \ \color{red}\text{(mod is a prime)}

  2. Dijkstra

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
struct edge{
    int v,w;
}; 
struct node{
    int x,d;
    friend bool operator < (node tmp_x,node tmp_y){
        return tmp_x.d>tmp_y.d;
    }
};
vector<edge>e[100001];
int dis[100001],vis[100001];
priority_queue<node>q;
void dijkstra(int n,int s){
    memset(dis,0x3f,sizeof(dis));
    while(!q.empty())q.pop();
    q.push({s,0});
    dis[s]=0;
    while(!q.empty()){
        int now=q.top().x;
        q.pop();
        if(!vis[now]){
            vis[now]=1;
            for(auto ed:e[now]){
                int v=ed.v;
                int w=ed.w;
                if(dis[v]>dis[now]+w){
                    dis[v]=dis[now]+w;
                    q.push({v,dis[v]});
                }
            }
        }
    }
}
  1. SPFA
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
struct edge{
    int v,w;
};
struct node{
    int x,d;
};
vector<edge>G[200005];
queue<int>q;
int dis[200005];
int vis[200005];
int tot[200005];
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(tot,0,sizeof(tot));
    while(!q.empty())q.pop();
    q.push(1);
    dis[1]=0;
    vis[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto i:G[u]){
            if(dis[i.v]>dis[u]+i.w){
                dis[i.v]=dis[u]+i.w;
                tot[i.v]=tot[u]+1;
                if(tot[i.v]>=n){
                    return true;
                }
                q.push(i.v);
                vis[i.v]=1;
            }
        }
    }
    return false;
}
  1. Kruskal
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
//不要忘记并查集初始化!!!
#define int long long
int n,m;
struct edge{
    int u,v,w;
}G[1000001];
int fa[1000001];
int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
bool cmp(edge _1,edge _2){
    return _1.w<_2.w;
}
int Kruskal(){
    int ans=0,tot=0;
    for(int i=1;i<=m;i++){
        int fx=find(G[i].u);
        int fy=find(G[i].v);
        if(fx!=fy){
            fa[fx]=fy;
            ans+=G[i].w;
            tot++;
            if(tot==n-1){
                return ans;
            }
        }
    }
    return -1;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>G[i].u>>G[i].v>>G[i].w;
    }
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    sort(G+1,G+m+1,cmp);
    int tmp=Kruskal();
    if(tmp==-1)cout<<"orz"<<endl;
    else cout<<tmp<<endl;
    return 0;
}