CDOJ 42/BZOJ 2753 滑雪与时间胶囊 kruskal

Green

2753: [SCOI2012]滑雪与时间胶囊
Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 1376  Solved: 487
[Submit][Status][Discuss]

Description
a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号i（1<=i<=N）和一高度Hi。a180285能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边，且i 的高度不小于j。 与其他滑雪爱好者不同，a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是a180285 滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。 现在，a180285站在1号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间
胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？

Input

输入的第一行是两个整数N，M。
接下来1行有N个整数Hi，分别表示每个景点的高度。
接下来M行，表示各个景点之间轨道分布的情况。每行3个整数，Ui，Vi，Ki。表示
编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。

Output

输出一行，表示a180285最多能到达多少个景点，以及此时最短的滑行距离总和。 

Sample Input


3 3
3 2 1
1 2 1
2 3 1
1 3 10


Sample Output

3 2


HINT
【数据范围】

    对于30%的数据，保证 1<=N<=2000

    对于100%的数据，保证 1<=N<=100000

对于所有的数据，保证 1<=M<=1000000，1<=Hi<=1000000000，1<=Ki<=1000000000。
题解
分析一下，第一问就是BFS一下就好啦，第二问就是求一颗最小生成树
点数，那就直接BFS一发，然后顺手把边压进一个vector里面
然后把这个vector按照高度降序，边权升序排序
然后跑一发Kruskal，然后就A了
代码

//qscqesze
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define REP_C(i, n) for (int n____=n,i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=b,i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=a,i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<n;++i)
#define FOR_N(i, a, b) for (i=a;i<b;++i)
#define DWN_N(i, b, a) for (i=b-1;i>=a;--i)
#define REP_1_C(i, n) for (int n____=n,i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=b,i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=a,i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=n;++i)
#define FOR_1_N(i, a, b) for (i=a;i<=b;++i)
#define DWN_1_N(i, b, a) for (i=b;i>=a;--i)
#define REP_C_N(i, n) for (int n____=(i=0,n);i<n____;++i)
#define FOR_C_N(i, a, b) for (int b____=(i=0,b);i<b____;++i)
#define DWN_C_N(i, b, a) for (int a____=(i=b-1,a);i>=a____;--i)
#define REP_1_C_N(i, n) for (int n____=(i=1,n);i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (int b____=(i=a,b);i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (int a____=(i=b,a);i>=a____;--i)
#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define REP_S(i, str) for (char*i=str;*i;++i)
#define REP_L(i, hd, suc) for (int i=hd;i;i=suc[i])
#define REP_G(i, u) REP_L(i,hd[u],suc)
#define REP_SS(x, s) for (int x=s;x;x=(x-1)&s)
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)
#define REP_4(i, j, k, ii, n, m, l, nn) REP(i, n) REP(j, m) REP(k, l) REP(ii, nn)
#define REP_4_1(i, j, k, ii, n, m, l, nn) REP_1(i, n) REP_1(j, m) REP_1(k, l) REP_1(ii, nn)
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define LBD(A, x) (lower_bound(ALL(A), x) - A.begin())
#define UBD(A, x) (upper_bound(ALL(A), x) - A.begin())
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int((A).size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define PTT pair<T, T>
#define Ts *this
#define rTs return Ts
#define fi first
#define se second
#define re real()
#define im imag()
#define Rush for(int ____T=RD(); ____T--;)
#define Display(A, n, m) {            \
  REP(i, n){                  \
    REP(j, m-1) cout << A[i][j] << " ";   \
    cout << A[i][m-1] << endl;        \
  }                      \
}
#define Display_1(A, n, m) {          \
  REP_1(i, n){                \
    REP_1(j, m-1) cout << A[i][j] << " ";   \
    cout << A[i][m] << endl;        \
  }                      \
}
typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define RD(n) scanf("%d",&n)
#define RDD(n) scanf("%lf",&n)
#define RDLL(n) scanf("%lld",&n)
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 100001
#define eps 1e-9
const int inf=0x7fffffff;
#define pi 3.1415926535898
#define eps 1e-9
#define MOD 1000000007
#define MAXN 200100
#define N
#define M
//**************************************************************************************
struct Edge
{
  int x;
  int y;
  int z;
};

struct node
{
  int x;
  int v;
};
vector<node> edge[100001];
int p[100001];
int ran[100001];
int h[100001];
int n,m;
int ans=0;
int ans2=0;
vector<Edge> kiss;
bool cmp(Edge a,Edge b)
{
  if(h[a.y]==h[b.y])
    return a.z<b.z;
  else
    return h[a.y]>h[b.y];
}
int fin(int x)
{
  if(p[x]==x)
    return x;
  return p[x]=fin(p[x]);
}
void unite(int x,int y)
{
  x=fin(x);
  y=fin(y);
  if(x==y)
    return;
  if(ran[x]<ran[y])
    p[x]=y;
  else
  {
    p[y]=x;
    if(ran[x]==ran[y])
      ran[x]++;
  }
}
void add_edge(int a,int b,int c)
{
  if(h[a]>=h[b])
    edge[a].push_back({b,c});
  if(h[b]>=h[a])
    edge[b].push_back({a,c});
}
int vis[100001];
void bfs()
{
  queue<int> q;
  vis[1]=1;
  q.push(1);
  ans=1;
  while(!q.empty())
  {
    int a=q.front();
    //cout<<a<<endl;
    p[a]=a;
    ran[a]=0;
    q.pop();
    for(int i=0;i<edge[a].size();i++)
    {
      int u=edge[a][i].x;
      kiss.push_back({a,u,edge[a][i].v});
      if(vis[u])
        continue;
      ans++;
      vis[u]=1;
      q.push(u);
    }
  }
}
bool same(int x,int y)
{
  return fin(x)==fin(y);
}
LL kr()
{
  LL ans=0;
  std::sort(kiss.begin(),kiss.end(),cmp);
  /*
  REP(i,kiss.size())
  {
    cout<<kiss[i].x<<" "<<kiss[i].y<<" "<<kiss[i].z<<endl;
  }
  */
  REP(i,kiss.size())
  {
    if(same(kiss[i].x,kiss[i].y))
      continue;
    ans+=(LL)kiss[i].z;
    //cout<<p[kiss[i].x]<<" wwww "<<p[kiss[i].y]<<endl;
    //p[kiss[i].y]=kiss[i].x;
    unite(kiss[i].x,kiss[i].y);
  }
  return ans;
}
void init()
{
  RD(n),RD(m);
  REP_1(i,n)
    RD(h[i]);
  REP(i,m)
  {
    int a,b,c;
    RD(a),RD(b),RD(c);
    add_edge(a,b,c);
  }
}
int main()
{
  int n,m;
  init();
  bfs();
  cout<<ans<<" "<<kr()<<endl;
}