史泓语

UID: 197, 注册于 2024-7-16 21:32:23, 最后登录于 2025-12-14 14:10:08, 目前离线.

解决了 837 道题目，RP: 294.95 (No. 5)

♂

个人简介

佛祖保佑永无BUG

\\\\ \\ \\ \\ \\ \\ \\ \\ || || || || || || // // // // // // // ////
\\\\ \\ \\ \\ \\ \\ \\        _ooOoo_          // // // // // // ////
\\\\ \\ \\ \\ \\ \\          o8888888o            // // // // // ////
\\\\ \\ \\ \\ \\             88"'.'"88               // // // // ////
\\\\ \\ \\ \\                (| o_o |)                  // // // ////
\\\\ \\ \\                   O\  =  /O                     // // ////
\\\\ \\                   ____/'---'\____                     // ////
\\\\                    .'  \\|     |//  '.                      ////
//==                   /  \\|||  :  |||//  \                     ==\\
//==                  /  _||||| -:- |||||_  \                    ==\\
//==                  |   | \\\  -  /// |   |                    ==\\
//==                  | \_|  ''\---/''  |_/ |                    ==\\
//==                  \  .-\__  \-/  ___/-. /                    ==\\
//==                ___`. .'  /--.--\  `. . ___                  ==\\
//==             ."" '<  `.___\_<|>_/___.'  >' "".               ==\\
//==            | | :  `- \`.:`\ _ /`:.`/ - ` : | |              \\\\
////            \  \ '-.   \_ __\ /__ _/   .-' /  /              \\\\
////     ========'-.____`-.___\_____/___.-`____.-'========       \\\\
////                          '=---='                            \\\\
//// //   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   \\ \\\\
//// // //       佛祖保佑      永无BUG      永不修改         \\ \\ \\\\
//// // // // // // || || || || || || || || || || \\ \\ \\ \\ \\ \\\\

如何优雅骂迪奥李隽羽：

在你和我之间，只有一个人比你聪明。
难道你是莎士比亚的后代，莎比士妮亚。
你知道你和一盘屎有什么区别吗？你没盘子。
上帝给我们分脑子时，你在耳朵那排队。
你脑子唯一作用是把两只耳朵分开。
你一直在和知识赛跑，可知识没追上你的脚步。
如果我往你的左耳倒水，会从右耳流出来。
如果我往你的耳朵里倒水，你一定会说：“感谢续杯”。
如果爱因斯坦智商是249，那你比他还聪明一点。

小彩蛋：{[(1000*3-1)/2+0.5]/3+1-300}*2-152=cs李隽羽的名字。

冒泡排序

void BubbleSort(int n)
{
  for(int i=n;i>=1;--i)
  {
    for(int j=1;j<i;++j)
    {
      if(a[j]>a[j+1])
      {
        swap(a[j],a[j+1]);
      }
    }
  }
}

堆排序

void Heapify(int n,int i)
{
  int largest=i;
  int lson=2*i,rson=2*i+1;
  if(a[lson]>a[largest]&&lson<=n)
  {
     largest=lson;
  }
  if(a[rson]>a[largest****]&&rson<=n)
  {
    largest=rson;
  }
  if(largest!=i)
  {
    swap(a[largest],a[i]);
    Heapify(n,largest);
  }
}
void HeapSort(int n)
{
  for(int i=n/2;i>=1;--i)
  {
    Heapify(n,i);
  }
  for(int i=n;i>=1;--i)
  {
    swap(a[1],a[i]);
    Heapify(i-1,1);
  }
}

手写循环队列

const int N=(队列大小);
struct CircularQueue
{
  int head=0,tail=0;
  int size=0;
  int q[N];

  bool full(){           //判断队列是否为满 
	return size==N;
  }
  bool empty(){          //判断队列是否为空 
  	return size==0;
  } 
  void push(int x){      //入队     
    if(full()){
      cout<<"Error"<<endl;
    }
    q[tail]=x;
    tail=(tail+1)%N;
    size++;
    return;
  }
  void pop(){            // 出队 
    if(empty()){
      cout<<"Error"<<endl;
      return;
    }
    head=(head+1)%N;
    size--;
    return;
  }
  int Size(){            // 队列长度 
    return size;
  }
  int front(){           //获取队首元素 
    if(empty()){
      return -1;
    }
    return q[head];
  }
  int back(){            //获取队尾元素 
  	if(empty()){    
      return -1;
    }
    int index=(tail-1+N)%N;
    return q[index];
  }
  //void print(){
  	//暂未开发
  //}
  void scan(){         //输入
	int n;
  	while(cin>>n){
  		push(n);
	  }
  }
};
int main()
{
  return 0;
}

Dijkstra朴素算法-邻接矩阵

#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
const int N=1010;
int n,m;
int g[N][N];
int dist[N];
bool visited[N];
void dijkstra(int s){
  for(int i=0;i<n;++i){
    dist[i]=INF;
    visited[i]=false;
  }
  dist[s]=0;
  for(int i=0;i<n;++i){
    int u=-1;
    int mindist=INF;
    for(int j=0;j<n;++j){
      if(!visited[j]&&dist[j]<mindist){
        mindist=dist[j];
        u=j;
      }
    }
    if(u<0){
      break;
    }
    visited[u]=true;
    for(int v=0;v<n;++v){
      if(!visited[v]&&g[u][v]<INF){
        dist[v]=min(dist[v],dist[u]+g[u][v]);
      }
    }
  }
}
int main()
{
  int s;
  cin>>n>>m;
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      g[i][j]=INF;
    }
  }
  for(int i=1;i<=m;++i){
    int u,v,w;
    cin>>u>>v>>w;
    g[u][v]=w;
  }
  cin>>s;
  dijkstra(s);
  for(int i=0;i<n;++i){
    if(dist[i]==INF){
      cout<<-1;
    }else{
      cout<<dist[i];
    }
    cout<<' ';
  }
  return 0;
}

Dijkstra朴素算法-邻接表

#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
const int N=1010;
int n,m;
struct Edge{
  int to,w;
};
vector<Edge> edge[N];
int dist[N];
bool visited[N];
void dijkstra(int s){
  for(int i=0;i<n;++i){
    dist[i]=INF;
    visited[i]=false;
  }
  dist[s]=0;
  for(int i=0;i<n;++i){
    int u=-1;
    int mindist=INF;
    for(int j=0;j<n;++j){
      if(!visited[j]&&dist[j]<mindist){
        mindist=dist[j];
        u=j;
      }
    }
    if(u<0){
      break;
    }
    visited[u]=true;
    for(int k=0;k<edge[u].size();++k){
      int v=edge[u][k].to;
      int w = edge[u][k].w;
      if(dist[v]>dist[u]+w){
        dist[v]=dist[u]+w;
      }
    }
  }
}
int main()
{
  int s=0;
  cin>>n>>m;
  for(int i=1;i<=m;++i){
    int u,v,w;
    cin>>u>>v>>w;
    edge[u].push_back({v,w});
  }
  dijkstra(s);
  for(int i=0;i<n;++i){
    if(dist[i]==INF){
      cout<<-1;
    }else{
      cout<<dist[i];
    }
    cout<<' ';
  }
  return 0;
}

Dijkstra堆优化算法-邻接表

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int INF=1e9;
const int N=1005;
struct Edge{
  int to,w;
};
vector<Edge> adj[N];
int dist[N];
bool vis[N];
int n,m;
void dijkstra(int s) {
  for(int i=0;i<n;i++){
    dist[i]=INF;
    vis[i]=false;
  }
  dist[s]=0;
  priority_queue<pii,vector<pii>,greater<pii>> heap;
  heap.push({0, s});
  while(!heap.empty()){
    int d=heap.top().first;
    int u=heap.top().second;
    heap.pop();
    if(vis[u]) continue;
    vis[u]=true;
    for(int i=0;i<adj[u].size();i++){
      int v=adj[u][i].to;
      int w=adj[u][i].w;
      if(dist[v]>dist[u]+w){
        dist[v]=dist[u]+w;
        heap.push({dist[v],v}); 
      }
    }
  }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
      int u,v,w;
      cin>>u>>v>>w;
      adj[u].push_back({v,w});
    }
    int s;
    cin>>s;
    dijkstra(s);
    for(int i=0;i<n;i++){
      if(dist[i]==INF) cout<<"INF ";
      else cout<<dist[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Prim堆优化算法-邻接表

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int INF=1e9;
const int N=1005;
struct Edge{
  int to,w;
};
vector<Edge> adj[N];
int dist[N];
bool vis[N];
int n,m;
void dijkstra(int s) {
  for(int i=0;i<n;i++){
    dist[i]=INF;
    vis[i]=false;
  }
  dist[s]=0;
  priority_queue<pii,vector<pii>,greater<pii>> heap;
  heap.push({0, s});
  while(!heap.empty()){
    int d=heap.top().first;
    int u=heap.top().second;
    heap.pop();
    if(vis[u]) continue;
    vis[u]=true;
    for(int i=0;i<adj[u].size();i++){
      int v=adj[u][i].to;
      int w=adj[u][i].w;
      if(dist[v]>dist[u]+w){
        dist[v]=dist[u]+w;
        heap.push({dist[v],v}); 
      }
    }
  }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
      int u,v,w;
      cin>>u>>v>>w;
      adj[u].push_back({v,w});
    }
    int s;
    cin>>s;
    dijkstra(s);
    for(int i=0;i<n;i++){
      if(dist[i]==INF) cout<<"INF ";
      else cout<<dist[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Bellman-Ford

#include<bits/stdc++.h>
using namespace std;
int INF=1e9;
struct Edge{
  int u,v,w;
};
int main()
{
int n,m;
cin>>n>>m;
vector<Edge> edge(m+1);
vector<int> dist(n+1,INF);
for(int i=1;i<=m;++i){
  cin>>edge[i].u>>edge[i].v>>edge[i].w;
}
dist[1]=0;
for(int i=1;i<=n-1;++i){
  for(int j=1;j<=m;++j){
    int u=edge[j].u;
    int v=edge[j].v;
    int w=edge[j].w;
    if(dist[u]!=INF){
    dist[v]=min(dist[v],dist[u]+w);
    }
  }
}
bool f=0;
for(int j=1;j<=m;++j){
  int u=edge[j].u;
  int v=edge[j].v;
  int w=edge[j].w;
  if(dist[u]!=INF&&dist[v]>dist[u]+w){
    f=1;
    break;
  }
}
if(f){
  cout<<"有负权回路"<<endl;
  return 0;
}
for(int i=1;i<=n;++i){
  if(dist[i]==INF){
    cout<<"无法到达";
  }else{
    cout<<dist[i];
  }
  cout<<' ';
}
return 0;
}

SPFA(Bellman-Ford队列优化版本)

#include<bits/stdc++.h>
using namespace std;
struct Edge{
  int to,w;
};
const int INF=1e9;
vector<Edge> adj[10005];
int dist[1005];
bool vis[1005];
int n,m;
int main()
{
  cin>>n>>m;
  for(int i=1;i<=m;++i){
    int u,v,w;
    cin>>u>>v>>w;
    adj[u].push_back({v,w});
  }
  for(int i=1;i<=n;++i){
    dist[i]=INF;
    vis[i]=false;
  }
  queue<int> q;
  dist[1]=0;
  q.push(1);
  vis[1]=true;
  while(!q.empty()){
    int u=q.front();
    q.pop();
    vis[u]=false;
    for(int i=0;i<adj[u].size();i++){
      int v=adj[u][i].to;
      int w=adj[u][i].w;
      if(dist[v]>dist[u]+w){
        dist[v]=dist[u]+w;
        if(!vis[v]){
          q.push(v);
          vis[v]=true;
        }
      }
    }
  }
  for(int i=1;i<=n;++i){
    if(dist[i]==INF){
      cout<<INF<<' ';
    }else{
      cout<<dist[i]<<' ';
    }
  }
  return 0;
}

最近活动

史泓语

个人简介

佛祖保佑 永无BUG

如何优雅骂迪奥李隽羽：

最近活动

状态

还没有账户？

登录

佛祖保佑永无BUG