#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=100010;

int n,m;
int h[N],w[N],ne[N],e[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void spfa(){
    memset(dist,0x3f,sizeof dist);
    queue<int> q;
    dist[1]=0;

    q.push(1);
    st[1]=true;

    while(q.size()){
        int t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];

            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

}



int main(void){
    cin>>n>>m;
    memset(h,-1,sizeof h);


    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);
    }

    spfa();

    int t=dist[n];

    if(t==0x3f3f3f3f)   puts("impossible");
    else cout<<t;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=210,INF=1e9;

int n,m,k;
int g[N][N];

void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

}

int main(void){
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j)    g[i][j]=0;
            else g[i][j]=INF;



    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }

    floyd();

    while(k--){
        int a,b;
        scanf("%d%d",&a,&b);

        if(g[a][b]>INF/2)    puts("impossible");
        else    printf("%d\n",g[a][b]);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=100010,M=200010,INF=0x3f3f3f3f;

struct Edge{
    int a,b,w;
}edges[M];

int n,m;
int p[N];

bool cmp(struct Edge A,struct Edge B){
    return A.w<B.w;
}

int find(int a){
    if(p[a]!=a) p[a]=find(p[a]);
    return p[a];
}


int kruskal(){
    for(int i=1;i<=n;i++)   p[i]=i;

    int res=0,cnt=0;
    for(int i=0;i<m;i++){
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;

        a=find(a);
        b=find(b);
        if(a!=b){
            p[a]=b;
            res+=w;
            cnt++;
            }
    }
    if(cnt<n-1) return INF;

    return res;
}

int main(void){
    cin>>n>>m;

    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }

    sort(edges,edges+m,cmp);

    int res=kruskal();

    if(res==INF)    cout<<"impossible";
    else cout<<res;

    return 0;
}

Prim算法解析

实现定义：假设G=（V，{E}）是连通图，TE是G上最小生成树中边的集合。算法从顶点集U={u0}(u0 ∈ V)，TE={}开始。重复执行下述操作：在所有v ∈ V-U的顶点中找到一条到集合U权重最小的边(u,v)并入集合TE，同时v并入顶点集U，直到U=V为止，此时TE必有n-1条边。（顶点v到集合U的距离指的是还未加入集合U的顶点v和集合U里所有与v连通的顶点中权重最小的那条边）

简而言之–寻找到到当前集合最近的顶点，再用该顶点更新所有点到集合距离，周而复始。

图解
https://gitee.com/mysterious-chinese-strongman/drawing-bed/raw/master/IMG_0738.jpg
实在不会上传图片QAQ

题目描述

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。由 V中的全部 n个顶点和 E中 n−1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G的最小生成树。

输入格式
第一行包含两个整数 n和 m。
接下来 m行，每行包含三个整数u,v,w，表示点u和点 之间存在一条权值为w的边。

样例

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

朴素Prim算法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=510, INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim(){
    int res=0;

    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1 || dist[j]<dist[t]))        //特判，如果是第一次进入这个循环，则只需要寻找到未被使用的顶点即可，否则选出当前距离集合最近的点
                t=j;                                        

        if(i && dist[t]==INF) return INF;       //特判，如果是第一次选结点进入集合，则所有结点到集合的距离都是INF，此时不需要执行该语句
                                                //如果找到的顶点距离集合为INF，说明这个图不是一个连通图，故不存在最小生成树

        if(i)   res+=dist[t];               //特判，如果是第一次选结点进入集合，则此时还没有边在集合中。否则将该边加入集合

        st[t]=true;

        for(int j=1;j<=n;j++)   dist[j]=min(dist[j],g[j][t]);   //用选中的顶点更新其他点到集合的距离
    }
    return res;
}

int main(void){
    cin>>n>>m;

    memset(g,0x3f,sizeof g);
    memset(dist,0x3f,sizeof dist);

    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;

}

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=510, INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim(){
    int res=0;

    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1 || dist[j]<dist[t]))
                t=j;

        if(i && dist[t]==INF) return INF;

        if(i)   res+=dist[t];

        st[t]=true;

        for(int j=1;j<=n;j++)   dist[j]=min(dist[j],g[j][t]);
    }
    return res;
}

int main(void){
    cin>>n>>m;

    memset(g,0x3f,sizeof g);
    memset(dist,0x3f,sizeof dist);

    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;

}

图

图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，表示为G(V,E)  翻译一下Graph(Vertex,Edge)

    注意点：(1)线性表中数据元素称为元素，树中数据元素称为结点，图中的数据元素称为顶点
           (2)图中不允许没有顶点，即顶点集合V有穷非空，但边集V可以是空的。

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对（Vi，Vj）来表示
无向图：如果图中所有的边都是无向边，则称该图为无向图
无向完全图：无向图中任意两个顶点之间都存在边，称为完全无向图。含n个顶点的完全无向图有n*(n-1)/2条边

有向边：若有顶点Vi指向Vj的边，则称这条边为有向边，，用有序偶对<Vi，Vj>来表示
有向图：如果图中所有的边都是有向边，则称该图为有向图（显而易见hh）
有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条有向边，则称为有向完全图，共有n*(n-1)条边

简单图：若不存在从一个节点出发，可以回到该点自身的边的集合（回环），且两个点之间不存在两个以上的边（重边）

稀疏图：边不多
稠密图：边很多

顶点的度：无向图中和该顶点想关联的边的数目

出度：在有向图中该顶点被指向的箭头个数，就是它的入度
入度：在有向图中从这个顶点指出去的箭头个数，就是它的出度

    性质：出度和等于入度和

路径：从一个顶点到另一个顶点所经历的顶点序列，路径的长度是路径上边的数目
回路（环）：第一个顶点和最后一个顶点相同的路径称为回路

子图：
连通图：在无向图G中。如果从顶点v1到顶点v2有路径，则称v1和v2是连通的，如果对于图中任意两个顶点都是联通的，则该图称为连通图。
连通分量：无向图中的最大连通子图称为连通分量

强连通图：在有向图中，如果从任意两个顶点v1和v2，都分别有v1到v2的路径和v2到v1到路径，则称为强连通图
强连通分量：

连通图的生成树：一个连通图的生成树是一个极小连通子图，它含有图中的n个顶点，但只有足以构成一棵树的n-1条边。

图的遍历

概念：从图中某一顶点出发访遍图中其余结点，且使每一个顶点仅被访问一次，这一过程称为图的遍历

深度优先遍历（DFS）：选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。
广度优先遍历（BFS）：首先把起点相邻的几个点探索完成，然后去探索距离起点稍远一些（隔一层）的点，然后再去玩探索距离起点更远一些（隔两层）的点，是一层一层的向外探索。

最小生成树

概念：构造连通图的最小代价生成树称为最小生成树

Prim算法：以某顶点为起点，逐步寻找各个顶点上最小权值的边来构建最小生成树
Kruskal算法：将所有边按从小到大排序，逐步选中最小权值的边，构建时需要考虑是否会形成环路

最短路径

概念：对于网图来说，最短路径指的是两顶点之间经过的边上权值之和最小的路径。

Dijkstra算法：基于已经求出的最短路径的基础上，求得更远顶点的最短路径
Flyod算法：每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径

最近看y总图论那里理论方面有点忘记，就记录下，先把算法详细写完再把这篇更完，有错的话大家指教下

树

度：树中结点拥有的子树个数称为结点的度

分支结点：度不为0度结点称为分支结点。
叶结点：度为0的结点称为叶结点，即终端结点

树的度：树内个节点的度的最大值
树的高度：树中结点的最大层次（根结点为第一层）称为树的高度

有序树：如果将树中结点的各子树堪称从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序数

森林：森林是m棵互不相交的树的集合

二叉树

二叉树定义：本身是有序树（左右子树不能互换），并且树中包含的各个节点的度不能超过 2，即只能是 0、1或者 2（这里的1可以是左子树也可以是右子树）

斜树：所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树（可以理解为线性表）

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上。

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层所有的结点都**连续**集中在最左边

二叉树性质

**性质1**:在二叉树的第i层最多有2^(i-1)个结点

证明：  由题可知，易证，cnt[i]=2^(i-1);

**性质2**:深度为k的二叉树最多有2^k-1个结点

证明：  等比数列求和公式Sn=a1(1-q^n)/(1-q)

**性质3**:对任何一棵二叉树T，如果其叶子结点个数为n0，度为2的结点个数为n2，则n0=n2+1

证明：   一棵二叉树中只有度分别为0，1，2的三种结点
        设度为1的节点有n1个，则树T的总结点数n=n0+n1+n2

        又因为共有n个结点，则共有n-1条连线（总有一条连线指向除了根结点的结点-除根结点每个结点只有一个父亲）
        度为2的结点连出去两条，度为1的结点连出去一条，则连线数也可以算作

        故有2*n2+1*n1+0*n0=n-1==n0+n1+n2-1  -->  n0=n2+1

**性质4**:具有n个结点的完全二叉树的深度为|log2(n)|+1

证明：   设完全二叉树的高度为x，因为完全二叉树的究极形态是x层的满二叉树，最弱形态是x-1层多一个，满二叉树的结点个数为2^x-1
        则可列出n<=2^x-1    又因为这里n和x都是整数，所以n<2^x   得x>log2(n);
               n>=2^(x-1)-1+1  得x<=log2(n)+1  
        又因为x是整数，故只能是|log2(n)|+1（这里是向下取整）


**性质5**:如果对一棵具有n个结点的完全二叉树的结点按层序进行编号，则
      (1)如果i=1，则结点i为二叉树根结点，如果i>1,则其父结点为i/2（向下取整），2*i是其左子树，2*i+1是其右子树
      (2)如果2*i>n,则结点i无左子树（为叶子结点），否则其左子树是结点2*i
      (3)如果2*i+1>n,则结点i无左子树，否则其右子树是结点2*i+1

二叉树的遍历

概念：二叉树的遍历是指从根结点出发，按照某种次序一次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次

**前序遍历**：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

**中序遍历**：若二叉树为空，则空操作返回，否则先中序遍历左子树，再访问根结点，再中序遍历右子树

**后序遍历**：若二叉树为空，则空操作返回，否则从左到右先叶子结点后根结点的方式遍历访问左右子树，最后访问根结点

**层序遍历**：若二叉树为空，则空操作返回，否则从根结点开始逐层访问，每一层从左到右遍历结点。

因为老是忘记，就想着做个笔记，写的不好，不吝赐教

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> get_divisors(int x){
    vector<int> res;

    for(int i=1;i<=x/i;i++){
        if(x%i==0){
            res.push_back(i);
            if(i!=x/i) res.push_back(x/i);
        }
    }
    sort(res.begin(),res.end());

    return res;
}


int main(void){
    int x,n;
    cin>>n;

    while(n--){
        cin>>x;
        auto res=get_divisors(x);

        for(auto x:res) cout<<x<<' ';
        puts("");
    }

    return 0;
}

//在一个数的质因子分解式中，出现的质数本身的值为底数，它出现的次数称为指数

//一个合数一定可以分解为若干质数的积，则第一个最小的约数一定是质数（反证法）

#include <iostream>

using namespace std;

void divide(int x){
    for(int i=2;i<x/i;i++){
        if(x%i==0){
            int s=0;
            while(x%i==0){
                x/=i;
                s++;
            }  
            cout<<i<<' '<<s<<endl;
        }
    }
    if(x>1) cout<<x<<' '<<'1'<<endl;
    puts("");
}

int main(void){
    int x,n;
    cin>>n;

    while(n--){
        cin>>x;
        divide(x);
    }

    return 0;
}

#include <iostream>

using namespace std;

bool is_prime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)  return false;
    return true;
}

int main(void){
    int x,n;
    cin>>n;

    while(n--){
        cin>>x;
        if(is_prime(x)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}