头像

战鹰战鹰我三岁啦

骑手战鹰正在偷吃你的卤肉饭




离线:2天前


最近来访(8)
用户头像
月影几度凉
用户头像
Anohgy
用户头像
Mine_
用户头像
有情人终成兄妹
用户头像
杰梦舒
用户头像
NoPassCet-6

活动打卡代码 AcWing 851. spfa求最短路

#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;
}




活动打卡代码 AcWing 854. Floyd求最短路

#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

二叉树的遍历

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

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

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

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

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

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



活动打卡代码 AcWing 869. 试除法求约数

#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;
}


活动打卡代码 AcWing 867. 分解质因数

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

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

#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;
}