P3366 【模板】最小生成树

admin

https://www.luogu.org/problemnew/show/P3366

题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入输出格式
输入格式：
第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：
输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例
输入样例#1：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出样例#1：
7
说明
时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. const int M=5010;
   
4. int n,m,x,y,len=0;
   
5. int a[M][M],ans,mina,pos;
   
6. bool visit[M],flag;
   
7. int main()
   
8. {
   
9.     cin>>n>>m;
   
10.     for(int i=1; i<=n; i++)
    
11.         for(int j=1; j<=n; j++)
    
12.             a[i][j]=999999;
    
13.     for(int i=1; i<=m; i++)
    
14.     {
    
15.         cin>>x>>y;
    
16.         int pi;
    
17.         cin>>pi;
    
18.         if(a[x][y]>pi)
    
19.         {
    
20.             a[x][y]=pi;
    
21.             a[y][x]=a[x][y];
    
22.         }
    
23.     }
    
24.     for(int i=1; i<=n; i++)
    
25.         a[i][i]=0;
    
26.     while(len<n)
    
27.     {
    
28.         mina=9999;
    
29.         for(int i=1; i<=n; i++)
    
30.         {
    
31.             if(visit[i])
    
32.                 continue;
    
33.             if(a[1][i]<mina)
    
34.             {
    
35.                 mina=a[1][i];
    
36.                 pos=i;
    
37.             }
    
38.         }
    
39.         //    cout<<pos<<" ";
    
40.         ans+=mina;
    
41.         visit[pos]=1;
    
42.         len++;
    
43.         for(int i=1; i<=n; i++)
    
44.         {
    
45.             if(visit[i])
    
46.                 continue;
    
47.             if(a[pos][i]<a[1][i])
    
48.                 a[1][i]=a[pos][i];
    
49.         }
    
50.     }
    
51.     cout<<ans<<endl;
    
52.     return 0;
    
53. }
    

复制代码

倚窗倾听风吹雨

还可以用堆排优化，emmm，太懒懒得打了，能AC就行