fork download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<queue>
  4. #include<set>
  5. #include<algorithm>
  6. using std::queue;
  7. typedef long long LL;
  8. const int N=100000+10;
  9. const int M=1000000+10;
  10. int n,m,h[N];
  11. struct EG{int x,y,z;}edge[M*2];
  12. int L;
  13. int vis[N];
  14. struct Link{int y,z;Link *next;}*head[N];
  15. int f[N];
  16.  
  17. void add_edge(int x,int y,int z)
  18. {
  19.     edge[L++]=(EG){x,y,z};
  20.     Link *p=new Link;
  21.     p->y=y; p->z=z;
  22.     p->next=head[x];
  23.     head[x]=p;
  24. }
  25.  
  26. int bfs()
  27. {
  28.     queue<int> Q;
  29.     int number=0;
  30.     Q.push(1); vis[1]=1;
  31.     while(!Q.empty())
  32.     {
  33.         int x=Q.front();Q.pop();
  34.         if((++number)==n) return number;
  35.         for(Link *p=head[x];p;p=p->next)
  36.             if(!vis[p->y])
  37.             {
  38.                 vis[p->y]=1;
  39.                 Q.push(p->y);
  40.             }
  41.     }
  42.     return number;
  43. }
  44.  
  45. bool cmp(EG a,EG b)
  46. {
  47.     if(h[a.y]==h[b.y]) return a.z<b.z;
  48.     return h[a.y]>h[b.y];
  49. }
  50.  
  51. int getroot(int x) { return f[x]==x ? x : f[x]=getroot(f[x]); }
  52. inline void merge(int x,int y) { f[getroot(x)]=getroot(y); }
  53.  
  54. LL solve()
  55. {
  56.     for(int i=1;i<=n;i++) f[i]=i;
  57.     std::sort(edge,edge+L,cmp);
  58.     LL tot=0;
  59.     for(int i=0;i<L;i++)
  60.     {
  61.         int x=edge[i].x;
  62.         int y=edge[i].y;
  63.         if(!vis[x] || !vis[y]) continue;
  64.         if(getroot(x)==getroot(y)) continue;
  65.         merge(x,y);
  66.         tot+=edge[i].z;
  67.     }
  68.     return tot;
  69. }
  70.  
  71. int main()
  72. {
  73.     scanf("%d%d",&n,&m);
  74.     for(int i=1;i<=n;i++) scanf("%d",&h[i]);
  75.     while(m--)
  76.     {
  77.         int a,b,c;
  78.         scanf("%d%d%d",&a,&b,&c);
  79.         if(h[a]>=h[b]) add_edge(a,b,c);
  80.         if(h[b]>=h[a]) add_edge(b,a,c);
  81.     }
  82.     printf("%d ",bfs());
  83.     printf("%lld\n",solve());
  84.     return 0;
  85. }
Success #stdin #stdout 0s 28440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 0
https://ideone.com/gDO8ud
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!