CSP-S 考前复习
2025-11-01 15:36:55
发布于：上海
69阅读
0回复
0点赞
1 三种最短路算法
Dijkstra
dijkstra堆优化版本_信奥算法普及/提高--ACGO题库
#include<bits/stdc++.h>
using namespace std;
int n,m,s = 1,u,v,w;
const int N = 1e5 + 10;
int dis[N],vis[N];
struct edge{
int dis,v;
friend bool operator < (edge a,edge b){
return a.dis > b.dis;
}
};
priority_queue<edge> q;
struct Node{
int weight,to;
};
vector<Node> g[N];
void dij(){
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
q.push({0,s});
while(!q.empty()){
edge t = q.top();
q.pop();
int x = t.v;
if(vis[x] == 1) continue;
vis[x] = 1;
for(int j = 0;j < g[x].size();j++){
int y = g[x][j].to;
int w = g[x][j].weight;
if(dis[y] > dis[x] + w){
dis[y] = dis[x] + w;
q.push({dis[y],y});
}
}
}
}
int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
cin >> u >> v >> w;
g[u].push_back({w,v});
}dij();
for(int i = 1;i <= n;i++){
cout << dis[i] << " ";
}
return 0;
}
SPFA
#include<bits/stdc++.h>
using namespace std;
struct Node {
int z, q;
};
vector<Node>v[100005];
int dis[100005];
bool vis[100005];
queue<int>q;
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
v[x].push_back({ y,z });
}
for (int i = 0; i <= n + 1; i++) {
dis[i] = 1e9;
}
dis[s] = 0;
vis[s] = 1;
q.push(s);
while (!q.empty()) {
int k = q.front();
q.pop();
vis[k] = 0;
for (int i = 0; i < v[k].size(); i++) {
int to = v[k][i].z;
int len = v[k][i].q;
if (dis[to] > dis[k] + len) {
dis[to] = dis[k] + len;
if (!vis[to]) {
vis[to] = 1;
q.push(to);
}
}
}
}
cout << dis[t];
return 0;
}
Floyd
最短距离查询【Floyd】_信奥算法入门_官方-ACGO题库
#include<bits/stdc++.h>
using namespace std;
int dis[205][205];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = 1e9;
}
}
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
dis[x][y] = z;
}
for (int kk = 1; kk <= n; kk++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][kk] + dis[kk][j]);
}
}
}
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
dis[x][y] == 1e9 ? cout << "impossible" << '\n' : cout << dis[x][y] << '\n';
}
return 0;
}
2 几种背包
见【线性DP】问题模型总结
3 ST表和LCA
ST表
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, M = 50;
int a[N];
int f[N][M];
int find(int l, int r) {
int k = log2(r + 1 - l);
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int main() {
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
f[i][0] = a[i];
}
int k = log2(m);
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= m + 1 - (1 << j); i++) {
f[i][j] = min(f[i][j - 1], f[(1 << (j - 1)) + i][j - 1]);
}
}
while (n--) {
int a, b;
cin >> a >> b;
cout << find(a, b) << " ";
}
}
LCA
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, s;
vector<int> g[N];
int fat[N][20];//fa[u][i]：从u结点，跳2^i步的结点
int dep[N];//存储深度
void dfs(int now, int fa){
fat[now][0] = fa;
dep[now] = dep[fa] + 1;
for(int i = 1; i <= 19; i++){
fat[now][i] = fat[fat[now][i - 1]][i - 1];
}
for(auto v : g[now]){
//避免往上跳
if(v == fa) continue;
dfs(v, now);
}
}
int LCA(int x, int y){
//1、先将x,y跳到同一层
//不妨设dep[x] >= dep[y]
if(dep[x] < dep[y]) swap(x, y);
int dis = dep[x] - dep[y];
for(int i = 0; i <= 19; i++){
if(dis >> i & 1) x = fat[x][i];
}
if(x == y) return x;
//2、一起跳到LCA的下一层
for(int i = 19; i >= 0; i--){
//因为要跳到LCA的下一层，所以一定是不相等的
if(fat[x][i] != fat[y][i]){
x = fat[x][i], y = fat[y][i];
}
}
return fat[x][0];
}
int main(){
cin >> n >> m >> s;
for(int i = 1; i <= n - 1; i++){
int u, v;
cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
}
dfs(s, 0);
while(m--){
int a, b;
cin >> a >> b;
cout << LCA(a,b) << endl;//+_+
}
// for(int i = 1; i <= n; i++){
// for(int j = 0; j < 20; j++){
// cout << fat[i][j] << " ";
// }
// cout << endl;
// }
return 0;
}
/*
1、处理出深度数组
2、处理出存储跳了2^i步的父亲结点 ST表
3、利用ST表求LCA
9 1 1
1 5
1 4
5 2
5 6
5 7
6 3
6 8
3 9
*/
4 归并排序，找逆序对
归并排序
#include<iostream>
using namespace std;
int n;
int m[1050];
void sort(int la, int ra, int lb, int rb) {
int i = la, j = lb, cnt = 0;
int srt[1050];
while (i <= ra && j <= rb) {
if (m[i] <= m[j]) srt[++cnt] = m[i++];
else srt[++cnt] = m[j++];
}
while (i <= ra) srt[++cnt] = m[i++];
while (j <= rb) srt[++cnt] = m[j++];
for (int i = 1; i <= cnt; i++) m[la + i - 1] = srt[i];
return;
}
void merge(int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
merge(l, mid);
merge(mid + 1, r);
sort(l, mid, mid + 1, r);
for (int i = 1; i <= n; i++) cout << m[i] << ' ';
cout << endl;
return;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> m[i];
merge(1, n);
return 0;
}
逆序对
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
long long ans;
int a[N], temp[N];
int n;
void merge(int l, int mid, int r) {
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else {
temp[k++] = a[j++];
ans += mid - i + 1;
}
}
while (i <= mid) {
temp[k++] = a[i++];;
}
while (j <= r) {
temp[k++] = a[j++];
}
for (int g = l; g <= r; g++) {
a[g] = temp[g];
}
}
void merge_sort(int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
merge(l, mid, r);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
merge_sort(1, n);
cout << ans << endl;
}
5 拓扑排序
#include<bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int n, m;
vector<int> g[N];
int in[N];
long long f[N];
int k[N];
queue<int> q;
void bfs() {
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i : g[u]) {
in[i]--;
f[i] += f[u];
if (!in[i]) {
q.push(i);
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
in[y]++;
k[x]++;
}
for (int i = 1; i <= n; i++) {
if (!in[i] && g[i].size()) {
f[i] = 1;
q.push(i);
}
}
bfs();
long long cnt = 0;
for (int i = 1; i <= n; i++) {
if (!k[i])
cnt += f[i];
}
cout << cnt;
}
6 STL容器的常用用法
（太多了，自己翻笔记去
7 并查集和最小生成树
并查集
#include<bits/stdc++.h>
using namespace std;
const int lt=200000;
int fa[lt+10];
int n,m;
int get(int x){
if(x == fa[x]){
return x;
}
return fa[x] = get(fa[x]);
}
void mer(int x,int y){
int fx = get(×), fy = get(y);
if (fx != fy) {
if (ranks[fx] > ranks[fy]) fa[fy] = fx;
else {
fa[fx] = fy;
if (ranks[fx] == ranks[fy]) ranks[fy]++;
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
fa[i] = i;
}
while(m--){
int z, x, y;
cin >> z >> x >> y;
if(z == 1){
if(get(x) != get(y)){
mer(x, y);
}
}else{
if(get(x) == get(y)){
cout << "Y" << "\n";
}else{
cout << "N" << "\n";
}
}
}
return 0;
}
最小生成树
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
int fa[N];
struct node {
int x, y, z;
}a[N];
bool cmp(node n, node m) {
return n.z < m.z;
}
int get(int x) {
if (fa[x] == x) {
return x;
}
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
int main() {
int n, m, ans = 0, cnt = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 0; i < m; i++) {
cin >> a[i].x >> a[i].y >> a[i].z;
}
sort(a, a + m, cmp);
for (int i = 0; i < m; i++) {
if (get(a[i].x) != get(a[i].y)) {
merge(a[i].x, a[i].y);
cnt++;
ans += a[i].z;
}
}
if (cnt == n - 1) {
cout << ans;
}
else {
cout << "orz";
}
return 0;
}
这里空空如也
有帮助，赞一个