华师一附中OI组

标题: P3366 【模板】最小生成树 [打印本页]
作者: admin    时间: 2018-5-4 10:02
标题: P3366 【模板】最小生成树
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
作者: 倚窗倾听风吹雨    时间: 2018-9-12 21:27
  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. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-9-12 21:28
还可以用堆排优化，emmm，太懒懒得打了，能AC就行



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2