HPU

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分钟前

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小时前

1≤n≤200,
1≤k≤n2
1≤m≤20000,

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小时前

1≤n≤2000,
1≤m≤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;
}

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

return 0;
}


16小时前

1≤n,m≤105,

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

2

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

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

return 0;
}



17小时前

1≤n,k≤500,
1≤m≤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小时前

1≤n≤105,
1≤m≤2∗105,

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

6

### 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小时前

1≤n≤500,
1≤m≤105,

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

6

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



1≤n,m≤1.5×105,

3 3
1 2 2
2 3 1
1 3 4

3

Dijkstra求最短路 I

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

cout << dijkstra() << endl;

return 0;
}



1≤n≤500,
1≤m≤105,

3 3
1 2 2
2 3 1
1 3 4

3

Dijkstra求最短路 II

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