• 个人简介

    杨奕淏是gay,杨奕淏喜欢小言,詹光胤,土豆,仔仔,雪碧,小新,Finn,小五,小杰😍😍😍全平台肘击桑境阳，支持者复制红字挂主页 全平台肘击桑境阳，支持者复制红字挂主页` 洛谷账号：chengyuhan13579

    image image

    image

    快速排序

    #include<bits/stdc++.h>
using namespace std;
vector<long long> v;
int i,j,temp;
void quicksort(int l,int r){
    if(l>r){
        return;
    }
    temp=v[l];
    i=l;
    j=r;
    while(i!=j){
        while(v[j]>=temp&&i<j){
            j--;
        }
        while(v[i]<=temp&&i<j){
            i++;
        }
        if(i!=j){
            swap(v[i],v[j]);
        }
    }
    swap(v[l],v[j]);
    quicksort(l,j-1);
    quicksort(i+1,r);
}
int main(){
    int n,x,cnt;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        v.push_back(x);
    }
    quicksort(0,n-1);
    for(int i=0;i<n;i++){
        cout<<v[i]<<' ';
    }
    return 0;
}

    归并排序

    #include<bits/stdc++.h>
using namespace std;
vector<int> s1,s2;
void marge(int l,int m,int r){
     s2.clear();
     int i=l,j=m+1;
     while(i<=m&&j<=r){
         if(s1[i]<s1[j]){
            s2.push_back(s1[i++]);
         }else{
            s2.push_back(s1[j++]);
         }
     }
     while(i<=m){
         s2.push_back(s1[i++]);
     }
     while(j<=r){
         s2.push_back(s1[j++]);
     }
     for(i=l;i<=r;i++){
        s1[i]=s2[i-l];
     }
}
void margesort(int a,int b){
     if(a==b){
       return;
     }
     int m=(a+b)/2;
     margesort(a,m);
     margesort(m+1,b);
     marge(a,m,b);
}
int main(){
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
       cin>>x;
       s1.push_back(x);
    }
    margesort(0,n-1);
    for(int i=0;i<n;i++){
       cout<<s1[i];
    }
    return 0;
}

    选择排序

    #include<bits/stdc++.h>
using namespace std;
void fun(int a[],int n){
     for(int i=0;i<n;i++){
        int minn=i;
        for(int j=i+1;j<n;j++){
          if(a[j]<a[minn]){
            minn=j;
          }
        }
     swap(a[i],a[minn]);
     }
}
int main(){
    int n,a[305];
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>a[i];
    } 
    fun(a,n);
    for(int i=0;i<n;i++){
      cout<<a[i];
    }
    return 0;
}

    插入排序

    #include<bits/stdc++.h>
using namespace std;
void insertsort(int a[],int n){
     int x;
     for(int i=1;i<n;i++){
        x=a[i];
        int j=0;
        for(j=i-1;j>=0;j--){
           if(a[j]>x){
             a[j+1]=a[j];
           }else{
             a[j+1]=x;
           }
        }
        if(j<0){
          a[0]=x;
        }
    }
}
int main(){
   int n,v[1005];
   cin>>n;
   for(int i=0;i<n;i++){
      cin>>v[i];
   }
   insertsort(v,n);
   for(int i=0;i<n;i++){
      cout<<v[i];
   }
   return 0;
}

    二分查找

    #include<bits/stdc++.h>
using namespace std;
int n,x,h;
vector<int> a;
int fun(){
    int l=1,r=n,v;
    while(l<r){
        v=(l+r)/2;
        if(a[v]>=x){
            r=v;
        }else{
            l=v+1;
        }
    }
    if(x==a[l]){
        return l;
    }else{
        return -1;
    }
}
int main(){
   cin>>n;
   for(int i=1;i<=n;i++){
      scanf("%d",&h);
      a.push_back(h);
   }
   cin>>x;
   printf("%d",fun()+1);
}

    堆排序

    #include<bits/stdc++.h>
using namespace std;
const int N=1e+6;
int n,a[N];
void heapify(int n,int i){
    int largest=i,lson=2*i,rson=2*i+1;
    if(a[largest]<a[lson]&&lson<=n){
        largest=lson;
    }
    if(a[largest]<a[rson]&&rson<=n){
        largest=rson;
    }
    if(a[i]!=a[largest]){
        swap(a[i],a[largest]);
        heapify(n,largest);
    }
}
void heapsort(){
    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);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    heapsort();
    for(int i=1;i<=n;i++){
        cout<<a[i];
    }
}

    image 以大根堆为例： 1、首先先找到最后一个非叶子结点，假设n个元素。 那么⌊n/2」 2、把完全二叉树自底向上修改成大根堆的形式，每修改一个数据，数组里面对应的数据需要随之变化。 3、当变成大根堆的时候，祖宗结点(a[1])一定是最大的，那么只需要和a[n]交换。总共有n个数，那么只需要n-1次就可以排完

    基数排序

    #include<bits/stdc++.h>
using namespace std;
const int N=1e+5;
int a[N],t[N];
int buchet[10];
void redixSort(int n){
    int max_val=*(max_element(a,a+n));
    int base=1;
    while(max_val/base>0){
        memset(buchet,0,sizeof(buchet));
        for(int i=0;i<n;i++){
            buchet[a[i]/base%10]++;
        }
        for(int i=1;i<10;i++){
            buchet[i]=buchet[i]+buchet[i-1];
        }
        for(int i=n-1;i>=0;i--){
            int v=a[i]/base%10;
            t[--buchet[v]]=a[i];
        }
        for(int i=0;i<n;i++){
            a[i]=t[i];
        }
        base*=10;
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",a+i);
    }
    redixSort(n);
    for(int i=0;i<n;i++){
        printf("%d",a[i]);
    }
    return 0;
}

    高精度减法

    #include<bits/stdc++.h>
using namespace std;
const int N=1e+6;
string a1,b1;
bool flag=false;
int a[N],b[N],c[N];
bool panduan(string s1,string s2){
    if(s1.size()!=s2.size()) return s1.size()<s2.size();
    else return s1<s2;
}
int main(){
    cin>>a1>>b1;
    if(panduan(a1,b1)){
        cout<<'-';
        swap(a1,b1);
    }
    for(int i=a1.size()-1,j=0;i>=0;i--,j++){
        a[j]=a1[i]-'0';
    }
    for(int i=b1.size()-1,j=0;i>=0;i--,j++){
        b[j]=b1[i]-'0';
    }
    int len=max(a1.size(),b1.size());
    for(int i=0;i<len;i++){
        c[i]+=a[i]-b[i];
        if(c[i]<0){
            c[i]+=10;
            c[i+1]--;
        }
    }
    for(int i=len-1;i>=0;i--){
        if(c[i]!=0){
            flag=true;
        }
        if(flag){
            cout<<c[i];
        }
    }
    if(flag==false){
        cout<<0;
    }
    return 0;
}

    高精度加法

    #include<bits/stdc++.h>
using namespace std;
int main(){
    string a1,b1;
    bool flag=0;
    int a[1000]={0},b[1000]{0},c[1000]={0};
    cin>>a1>>b1;
    for(int i=a1.size()-1,j=0;i>=0;i--,j++){
        a[j]=a1[i]-'0';
    }
    for(int i=b1.size()-1,j=0;i>=0;i--,j++){
        b[j]=b1[i]-'0';
    }
    for(int i=0;i<a1.size()||i<b1.size();i++){
        c[i]=a[i]+b[i];
    }
    for(int i=0;i<a1.size()||i<b1.size();i++){
        if(c[i]>=10){
            c[i]-=10;
            c[i+1]++;
        }
    }
    for(int i=max(a1.size()+1,b1.size()+1);i>=0;i--){
        if(c[i]!=0){
            flag=1;
        }
        if(flag){
            cout<<c[i];
        }
    }
}

    高精度除法(高精除高精)

    #include <bits/stdc++.h>
using namespace std;
int a[1005];
int c[1005];
long long s2;
long long r;
string s1;
int len = 0;
int main () {
    cin >> s1 >> s2;
    for (unsigned int i = 0;i < s1.size();++i)
    {
        a[i] = s1[i] - '0';
    }
    len =s1.size();
    for (int i = 0;i < len;++i)
    {
        c[i] = (r * 10 + a[i]) / s2;
        r = (r * 10 + a[i]) % s2;
    }
    int i = 0;
    while(c[i] == 0 && i < len - 1)
    {
        i++;
    }
    for (int j = i;j < len;++j)
    {
        cout << c[j];
    }
    return 0;
}

    高精度除法(高精除低精)

    #include<bits/stdc++.h>
using namespace std;
long long a[5005],c[5005],b;
bool flag=false;
int shuwei(int x){
    int i=0;
    while(x!=0){
        x/=10;
        i++;
    }
    return i;
}
int main(){
    string s1;
    cin>>s1>>b;
    for(int i=0;i<s1.size();i++){
        a[i]=s1[i]-'0';
    }
    if(a[0]==0||b==0||shuwei(b)>s1.size()){
        cout<<0;
        return 0;
    }
    for(int i=0;i<s1.size();i++){
        c[i]=a[i]/b;
        a[i+1]+=a[i]%b*10;
    }
    for(int i=0;i<s1.size();i++){
        if(c[i]!=0){
            flag=true;
        }
        if(flag){
            cout<<c[i];
        }
    }
}

    高精度乘法

    #include<bits/stdc++.h>
using namespace std;
int main(){
    string M,N;
    int m[500]={0},n[500]={0},c[10000]={0};
    bool flag=0;
    cin>>M>>N;
    if(M=="0"||N=="0"){
        cout<<0;
        return 0;
    }
    for(int i=M.size()-1,j=0;i>=0;i--,j++){
        m[j]=M[i]-'0';
    }
    for(int i=N.size()-1,j=0;i>=0;i--,j++){
        n[j]=N[i]-'0';
    }
    for(int i=0;i<N.size();i++){
        for(int j=0;j<M.size();j++){
            c[i+j]+=m[j]*n[i];
        }
    }
    for(int i=0;i<N.size()+M.size();i++){
        if(c[i]>=10){
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
    }
    for(int i=N.size()+M.size();i>=0;i--){
        if(c[i]!=0){
            flag=1;
        }
        if(flag){
            cout<<c[i];
        }
    }
}

    哈希算法

    #include<bits/stdc++.h>
using namespace std;
const int N=1e+5;
int hash1[N],HMAX,cnt[N],b[N];
void hashinit(int x){
    for(int i=1;i<=x;i++){
        hash1[i]=-1;
    }
}
void hashinsert(int x){
    int y=x%HMAX;
    while(1){
        if(hash1[y]==-1){
            hash1[y]=x;
            cnt[y]=1;
            return;
        }else if(hash1[y]==x){
            cnt[y]++;
            return;
        }
        if(++y>HMAX){
            y=1;
        }
    }
}
int hashget(int x){
    int y=x%HMAX;
    while(1){
        if(hash1[y]==-1){
            return 0;
        }else if(hash1[y]==x){
            return cnt[y];
        }
        if(++y>HMAX){
            y=1;
        }
    }
}
int main(){
    int x;
    cin>>HMAX;
    hashinit(HMAX);
    for(int i=1;i<=HMAX;i++){
        cin>>x;
        hashinsert(x);
    }
    //根据题目变化
    return 0;
}

    Dijkstra朴素算法

    #include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 1e9;
int n, m;
int g[N][N];
int dist[N];
bool visited[N];
void dijkstra(int start){
    for (int i = 0; i <= n; i++){
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 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 == -1){
            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(){
    cin >> n >> m;
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= n; j++){
            g[i][j] = (i == j ? 0 : INF);
        }
    }
    for (int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        if (w<g[a][b]&&a^b){
            g[a][b] = w;
        }
    }
    dijkstra(1);
    cout<<dist[n];
    return 0;
}

    希尔排序

    #include <bits/stdc++.h>
using namespace std;
const long long N=1e+5;
int a[N];
void shell_sort(int n){
    int gap=n/2;
    while(gap>0){
        for(int i=gap;i<n;i++){
            int temp=a[i];
            int j=i;
            while(j>=gap&&temp<a[j-gap]){
                a[j]=a[j-gap];
                j-=gap;
            }
            a[j]=temp;
        }
        gap/=2;
    }
}
int main(){
    int n;
    cin>>n;
    for (int i = 0; i < n; i++){
        cin>>a[i];
    }
    shell_sort(n);
    for (int i=0;i<n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

    手写栈

    #include<bits/stdc++.h>
using namespace std;
unsigned long long s[1000005],t;
void init(){
    t=0;
}
void push(unsigned long long x){
    s[++t]=x;
}
void pop(){
    if(t==0){
        puts("Empty");
    }else{
        t--;
    }
}
bool empty(){
    return t==0;
}
int top(){
    if(t==0){
        puts("Anguei!");
    }else{
        return s[t];
    }
}
int size(){
    return t;
}
int main(){
    
}

    手写队列

    #include<bits/stdc++.h>
using namespace std;
const int N=114514;
struct CircularQueue{
    int data[N],head=0,tail=0;
    int size(){
        return tail-head+1;
    }
    bool empty(){
        return tail==head;
    }
    int front(){
        return data[head%N];
    }
    int back(){
        return data[tail%N];
    }
    void push(int x){
        if((tail+1)%N!=head%N){
            data[tail++%N]=x;
        }
    }
    void pop(){
        if(!empty()){
          head++;
    }
    
};
int main(){
     
}

    单调队列

    #include<bits/stdc++.h>
using namespace std;
long long int a[1000005];
int n,k;
deque<int> d,x; 
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    for(int i=1;i<=n;i++){
        if(!x.empty()&&i-x.front()==k){
            x.pop_front();
        }
        while(!x.empty()&&a[x.back()]>a[i]){
            x.pop_back();
        }
        x.push_back(i);
        if(i>=k){
            printf("%lld ",a[x.front()]);
        }
    }
    printf("\n");
    for(int i=1;i<=n;i++){
        if(!d.empty()&&i-d.front()==k){
            d.pop_front();
        }
        while(!d.empty()&&a[d.back()]<a[i]){
            d.pop_back();
        }
        d.push_back(i);
        if(i>=k){
            printf("%lld ",a[d.front()]);
        }
    }
    return 0;
}

    广搜模板

    #include <bits/stdc++.h>
using namespace std;
#define MAX 200005
vector<int> graph[MAX];
bool visited[MAX];
int v,e;
void BFS(int bg){;
    queue<int> q;
    q.push(bg);
    visited[bg]=1;
    while (!q.empty()){
        int n=q.front();
        q.pop();
        cout<<n<<' ';
        for (int m=0,len=graph[n].size();m<len;m++){
            if (!visited[graph[n][m]]){
                q.push(graph[n][m]);
                visited[graph[n][m]]=1;
            }
        }
    }
}

int main(){
    cin>>v>>e;
    int n,m;
    for(int i = 0; i < e; ++i){
        cin>>n>>m;
        graph[n].push_back(m);
        graph[m].push_back(n);
    }
    int bg,end;
    cin>>bg>>end;
    BFS(bg);
    return 0;
}

    深搜模板

    #include<bits/stdc++.h>
using namespace std;
const int N=1e5;
bool visit[N];
void dfs(int root,int n){
	if(root==n){
		//找到一种结果，统计个数或输出路径
		return;
	}
	for(int i=root;i<n;i++){
		if(!visit[i]){//检查i是否用过
			visit[i]=1;//将i标记为用过
			dfs(root+1,n);
			visit[i]=0;//回溯，搜索过i后i就可以用了
		}
	}
}
int main(){
	//根据题目来写
	return 0;
}

    快读

    #include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    long long m,n,s2;
    bitset<1000000000> s;
    bool flag;
    m=read();
    n=read();
    for(int i=0;i<m;i++){
        s[read()]=1;
    }
}

    01背包

    #include <bits/stdc++.h>
using namespace std;
const int BAG = 105;
int dp[BAG][BAG];
int weight[BAG];
int value[BAG];
int main () {
    int n,bagweight;
    cin >> n >> bagweight;
    for(int i = 0;i < n;++i)
    {
        cin >> weight[i] >> value[i];
    }
    for(int j = weight[0];j <= bagweight;++j)
    {
        dp[0][j] = value[0];
    }
    for(int i = 1;i < n;++i)
    {
        for(int j = 1;j <= bagweight;++j)
        {
            if(j < weight[i])
            {
                dp[i][j] = dp[i - 1][j];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    for(int i = 0;i < n;++i)
    {
        for(int j = 0;j <= bagweight;++j)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

    Bellman--Ford(判断负权回路)

    #include<bits/stdc++.h>
using namespace std;
#define N 1e7
#define INF 1e7
struct edge{
    int u,v,w;
};
vector<edge> edges(N);
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        cin>>edges[i].u>>edges[i].v>>edges[i].w;
    }
    vector<int> dist(N,INF);
    dist[1]=0;
    bool flag=false;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int u=edges[j].u;
            int v=edges[j].v;
            int w=edges[j].w;
            if(dist[u]!=INF&&dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                if(i==n){
                    flag=true;
                }
            }
        }
    }
    if(flag){
        cout<<-1;
    }else{
        for(int i=1;i<=n;i++){
            if(dist[i]!=INF){
                cout<<dist[i]<<" ";
            }else{
                cout<<"INF ";
            }
        }
    }
    return 0;
}

    SPFA算法(判断负权回路）

    #include <bits/stdc++.h>
using namespace std;
#define MAX 1005
#define INF 1e7
struct edge{
    int v,w;
};
vector<edge> graph[MAX];
int dist[MAX],barrel[MAX];
bool visited[MAX];
int n,m;
bool find(){
    for(int i=0;i<n;i++){
        if(barrel[i]>=n) return true;
    }
    return false;
}
bool SPFA(int bg){
    for(int i=1;i<=n;i++){
        dist[i]=INF;
        barrel[i]=0;
        visited[i]=false;
    }
    dist[bg]=0;
    queue<int> q;
    q.push(bg);
    visited[bg]=true;
    while (!q.empty()){
        int n=q.front();
        q.pop();
        visited[n]=false;
        barrel[n]++;
        for (int m=0,len=graph[n].size();m<len;m++){
            int v=graph[n][m].v;
            int w=graph[n][m].w;
            if(dist[v]>dist[n]+w){
                dist[v]=dist[n]+w;
                if(visited[graph[n][m].v]==false){
                    q.push(graph[n][m].v);
                    visited[graph[n][m].v]=true;
                }
            }
            
        }
        if(find()){
            return false;
        }
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; ++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        graph[u].push_back({v,w});//双向图加graph[v].push_back({u,w});
    }
    if(SPFA(1)){
        for(int i = 1; i <= n; ++i){
            cout<<dist[i]<<' ';
        }
    }else{
        printf("-1");
    }
    return 0;
}

    dijkstra堆优化算法

    #include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 1e9;
int n,m,bg;
struct edge{
    int to,w;
};
vector<edge> g[N];
int dist[N];
bool visited[N];
void dijkstra(int start){
    for (int i = 0; i <= n; i++){
        dist[i] = INF;
        visited[i] = false;
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
    heap.push({0,start});
    dist[start] = 0;
    while (!heap.empty()){
        int n=heap.top().second;
        heap.pop();
        if(visited[n]) continue;
        visited[n]=true;
        for (int i=0,len=g[n].size();i<len;i++){
            int v=g[n][i].to;
            int w=g[n][i].w;
            if(!visited[v]&&dist[v]>dist[n]+w){
                dist[v]=dist[n]+w;
                heap.push({dist[v],v});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 0; i < m; i++){
        int a, b, w;
        scanf("%d%d%d",&a,&b,&w);
        g[a].push_back({b,w});
    }
    scanf("%d",&bg);
    dijkstra(bg);
    for(int i=1;i<=n;i++){
        dist[i]==INF?printf("INF "):printf("%d ",dist[i]);
    }
    return 0;
}

    欧拉筛(线性筛):O(n)

    #include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,cnt=0;
bool vis[N];
int prime[N];
void FindPrime(int n){
    for(int i=2;i<=n;i++){
        if(!vis[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<=n;j++){
            int k=prime[j];
            vis[k*i]=true;
            if(i%k==0) break;
        }
    }
}
int main(){
    scanf("%d",&n);
    FindPrime(n);
    for(int i=0;i<cnt;i++){
        printf("%d ",prime[i]);
    }
    return 0;
}

    埃氏筛:O(nloglongn)

    #include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
bool vis[N];
void FindPrime(int n){
    memset(vis,false,sizeof(vis));
    vis[0]=vis[1]=true;
    for(int i=2;i*i<=n;i++){
        if(!vis[i]){
            for(int j=i*i;j<=n;j+=i){
                vis[j]=true;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    FindPrime(n);
    for(int i=0;i<n;i++){
        if(!vis[i]){
            printf("%d ",i);
        }
    }
    return 0;
}

    最小生成树(堆优化+邻接表）

    #include <bits/stdc++.h>
using namespace std;
const int N = 10010;
const int INF = 1e9;
int n,m;
long long sum;
struct edge{
    int to,w;
};
vector<edge> g[N];
int dist[N];
bool visited[N];
void prim(int start){
    for (int i = 0; i <= n; i++){
        dist[i] = INF;
        visited[i] = false;
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
    heap.push({0,start});
    dist[start] = 0;
    while (!heap.empty()){
        int f=heap.top().second;
        heap.pop();
        if(visited[f]) continue;
        visited[f]=true;
        for (int i=0,len=g[f].size();i<len;i++){
            int v=g[f][i].to;
            int w=g[f][i].w;
            if(!visited[v]&&dist[v]>w){
                dist[v]=w;
                heap.push({dist[v],v});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 0; i < m; i++){
        int a, b, w;
        scanf("%d%d%d",&a,&b,&w);
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    prim(1);
    for(int i=1;i<=n;i++){
        if(dist[i]!=INF)sum+=dist[i];
    }
    printf("%lld",sum);
    return 0;
}

  • 最近活动

927
已递交
864
已通过
0
题解被赞
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 13ms