头像

以梦为马

HPU


访客:11776

离线:4分钟前


分享 数论

以梦为马
14分钟前

质数的判断

  1. 朴素做法 ---- $O(n^2)$
bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i < n; i ++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
  1. 改进版 ---- $O(\sqrt{n})$
bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i ++){//约数成对出现,i 和 n / i, 枚举到较小的那个即可. 
        if(n % i == 0){
            return false;
        }
    }
    return true;
}



以梦为马
19分钟前

题目描述

给定n个正整数ai,判定每个数是否是质数。

输入格式

第一行包含整数n。

接下来n行,每行包含一个正整数ai。

输出格式

共n行,其中第 i 行输出第 i 个正整数ai是否为质数,是则输出“Yes”,否则输出“No”。

数据范围

1≤n≤100,
1≤ai≤2∗109

输入样例:

2
2
6

输出样例:

Yes
No

主要考点

质数的判断

C ++ 代码

#include <iostream>
#include <algorithm>

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(){
    int n;
    cin >> n;
    while(n --){
        int a;
        cin >> a;
        if(is_prime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}



以梦为马
13小时前

题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输出“impossible”。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数n,m,k

接下来m行,每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

接下来k行,每行包含两个整数x,y,表示询问点x到点y的最短距离。

输出格式

共k行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出“impossible”。

数据范围

1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。

输入样例:

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例:

impossible
1

主要考点

floyd算法

C ++ 代码

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

using namespace std;
const int N = 210, INF = 0x3f3f3f3f;

int d[N][N];//d[i][j]表示i到j的距离
int n, m, k;

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

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

    //初始化
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    }

    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while(k --){
        int a, b;
        cin >> a >> b;
        if(d[a][b] > INF / 2) cout << "impossible" << endl;
        else cout << d[a][b] << endl;
    }

    return 0;
}



以梦为马
14小时前

题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式

如果图中存在负权回路,则输出“Yes”,否则输出“No”。

数据范围

1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过10000。

输入样例:

3 3
1 2 -1
2 3 4
3 1 -4

输出样例:

Yes

主要考点

spfa算法

C ++ 代码

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

using namespace std;
const int N = 2010, M = 10010;

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

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

bool spfa(){
    queue<int> q;
    for(int i = 1; i <= n; i ++){
        q.push(i);
        st[i] = 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];//注意是e[i],不少次写出ne[i],血的教训!
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if(cnt[j] >= n) return true;
                if(!st[j]){
                    q.push(j);
                    st[j] = true; 
                }
            }
        }
    }

    return false;
}

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

    memset(h, -1, sizeof h);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if(spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}



以梦为马
16小时前

题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式

输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出”impossible”。

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过10000。

输入样例:

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

输出样例:

2

主要考点

最短路spfa算法

C ++ 代码

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

using namespace std;
const int N = 100010;

int h[N], ne[N], e[N], idx, w[N];//邻接表
int dist[N];//dist[j]表示1号点到j号点的距离
bool st[N];//该点当前是否在队列当中
int n, m;

//建立一条a -> b的边,边权为 c
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa(){
    //初始化各点的距离
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;//1号点已经在队列当中
    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;
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

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

    memset(h, -1, sizeof h);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int t = spfa();
    if(t == -1) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}




以梦为马
17小时前

题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。

注意:图中可能存在负权回路

输入格式

第一行包含三个整数n,m,k。

接下来m行,每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式

输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径,则输出“impossible”。

数据范围

1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过10000。

输入样例:

3 3 1
1 2 1
2 3 1
1 3 3

输出样例:

3

主要考点

bellman_ford算法

C ++ 代码

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

using namespace std;
const int N = 510, M = 10010;

int n, m, k;
int dist[N];// d[j] 表示 1 号点到 j 号点的距离
int backup[N];// dist[]备份,防止数据发生串联

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

int bellman_ford(){
    //初始化
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    //迭代k次
    for(int i = 0; i < k; i ++){
        memcpy(backup, dist, sizeof dist);//防止数据发生串联
        for(int j = 0; j < m; j ++){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);//松弛操作
        }
    }
    if(dist[n] > 0x3f3f3f3f / 2) return -1;//最多减少10000 * 500
    return dist[n];
}

int main(){
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++){
        int a, b , w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int t = bellman_ford();
    if(t == -1) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}



以梦为马
19小时前

题目描述

给定一个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和点v之间存在一条权值为w的边。

输出格式

共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

数据范围

1≤n≤105,
1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过1000。

输入样例:

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

输出样例:

6

主要考点

最小生成树kruskal并查集

C ++代码

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

using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int p[N];//p[x]表示x的父节点

struct Edge{
    int a, b, w;
    bool operator < (const Edge &W) const{//按权重大小排序
        return w < W.w;
    }
}edges[N];

//返回x的父节点
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    //step1. 将所有边按权重大小从小到大排序
    sort(edges, edges + m);
    for(int i = 1; i <= m ; i ++) p[i] = i;//初始化并查集

    //step2. 枚举每条边a, b和权重c
    int res = 0, cnt = 0;//cnt表示加入边的个数
    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);
        //step3. 如果不连通将该边加入到集合当中
        if(a != b){
            p[a] = b;
            res += w;//最小生成树的权值之和
            cnt ++;
        }
    }
    if(cnt < n - 1) return INF;
    else return res;
}

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

    for(int i = 0; i < m; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    int t = kruskal();
    if(t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}



以梦为马
20小时前

题目描述

给定一个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和点v之间存在一条权值为w的边。

输出格式

共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

数据范围

1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过10000。

输入样例:

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

输出样例:

6

主要考点

最小生成树prim

C ++代码

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

using namespace std;
const int N = 510, INF = 0x3f3f3f3f;

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

int prim(){
    memset(dist, 0x3f, sizeof dist);//dist[i]初始化为正无穷

    int res = 0;
    for(int i = 0; i < n; i ++){
        //step1. 找到集合外距离集合最近的点
        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];

        //step2. 用t更新其他点
        for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]);

        //step3. st[t] = true
        st[t] = true;
    }
    return res;
}

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

    memset(g, 0x3f, sizeof g);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(c, g[a][b]);
    }

    int t = prim();
    if(t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}




题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为非负值

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式

输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出-1。

数据范围

1≤n,m≤1.5×105,
图中涉及边长均不小于0,且不超过10000。

输入样例:

3 3
1 2 2
2 3 1
1 3 4

输出样例:

3

主要考点

堆优化版的djkstra算法

姊妹题

Dijkstra求最短路 I

时间复杂度$O(m * logn)$

C ++ 代码

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

using namespace std;
typedef pair<int, int> PII;

const int N = 1.5 * 1e5 + 10;

//邻接表就是数组模拟链表,图中每个节点拉一条链,存储它所有的邻边'
//e[i]表示邻边的另一个端点,w[i]表示邻边长度,ne[i]表示链表的下一个节点下标,idx表示当前用到了哪个下标。
int h[N], e[N], ne[N], idx;
int dist[N];// 存储所有点到1号点的距离
bool st[N];
int w[N];
int n, m;

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

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while(heap.size()){
        PII t = heap.top();
        heap.pop();

        int distance = t.first, ver = t.second;
        if(ver == n) break;

        if(st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

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

    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b,c);
    }

    cout << dijkstra() << endl;

    return 0;
}




题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为正值

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式

输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出-1。

数据范围

1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例:

3 3
1 2 2
2 3 1
1 3 4

输出样例:

3

主要考点

朴素版dijkstra

姊妹题

Dijkstra求最短路 II

时间复杂度$O(n ^ 2)$

C ++ 代码

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

using namespace std;
const int N = 510;

int g[N][N];// 存储每条边的边权
int dist[N];//g[j] 存储 1 号点到 j号点的距离
bool st[N];//st[t]表示: t 号点是否已经更新过其他点
int n, m;

int dijkstra(){
    //初始化距离
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    //因为已经加入一号点
    for(int i = 0; i < n - 1; i ++){
        //寻找距离1号点最近的点
        int t = -1;//t用来求所有st[] == false的节点中,dist[]最小的节点编号
        for(int j = 1; j <= n; j ++){
            if(!st[j] && (t == -1 || dist[j] < dist[t])){
                t = j;
            }
        }

        // 用t更新其他点的距离
        for(int j = 1; j <= n; j ++){
            //1 号点通过 t号点到达 j 号点的最短距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }//本题中边权都为正数,dist[i] + g[i][i] 一定大于 dist[i],所以i->i这条边一定不会被用到。

        st[t] = true;//t已经用过,置为false
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

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

    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }

    cout << dijkstra() << endl;

    return 0;
}