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

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-) cout << A[i][j] << " ";     \

        cout << A[i][m-] << endl;                \

    }                                            \

}

#define Display_1(A, n, m) {                    \

    REP_1(i, n){                                \

        REP_1(j, m-) 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[];

int p[];

int ran[];

int h[];

int n,m;

int ans=;

int ans2=;

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[];

void bfs()

{

    queue<int> q;

    vis[]=;

    q.push();

    ans=;

    while(!q.empty())

    {

        int a=q.front();

        //cout<<a<<endl;

        p[a]=a;

        ran[a]=;

        q.pop();

        for(int i=;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]=;

            q.push(u);

        }

    }

}

bool same(int x,int y)

{

    return fin(x)==fin(y);

}

LL kr()

{

    LL ans=;

    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;

}

巴特西