P2573 [SCOI2012]滑雪

题目描述

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

输入输出格式

输入格式：

输入的第一行是两个整数 N,M 。

接下来 1行有 N个整数 Hi​ ，分别表示每个景点的高度。

接下来 M行，表示各个景点之间轨道分布的情况。每行 3 个整数， Ui,Vi,Ki。表示编号为 Ui的景点和编号为 Vi的景点之间有一条长度为 Ki 的轨道。

输出格式：

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

输入输出样例

输入样例#1： 

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

输出样例#1： 

3 2

说明

【数据范围】

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

对于 100%  的数据，保证 1≤N≤10⁵

对于所有的数据，保证 1≤M≤10⁶  , 1≤Hi≤10⁹， 1≤Ki≤10⁹  。

Solution：

　　本题ZYYS（吐槽：每次复制题面，都要炸markdown格式，好不爽啊，懒人不想改～）。

　　老鱼讲朱刘算法时提到这题，结果朱刘算法是本题暴力分？

　　正解：bfs+kruscal

　　我们先从1广搜，就能处理出最多能到达的点的个数，在bfs的同时，建一张新图，因为有向，所以要在新图中求最小树形图。

　　由于有高度限制（边有向），克鲁斯卡尔的排序过程就不能简单的按边权排序了，否则就会出现高度低的点指向高度高的点的情况，所以我们应该先让高度高的连向高度低的点，因为新图满足$H[u]geq H[v]$，于是按所到点的高度为第一关键字从大到小排序，边权为第二关键字从小到大排序，再做kruscal就是正确的了。

代码：

/*Code by 520 -- 8.21*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=2000005;
int n,m,to[N],net[N],w[N],h[N],cnt,H[N];
int fa[N],tot;
struct node{
    int u,v,w;
    bool operator < (const node &a)const{return H[v]==H[a.v]?w<a.w:H[v]>H[a.v];} 
}e[N];
bool vis[N];

int gi(){
    int a=0;char x=getchar();
    while(x<'0'||x>'9')x=getchar();
    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+(x^48),x=getchar();
    return a;
}

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,w[cnt]=c;}

void bfs(){
    queue<int>q;
    q.push(1),vis[1]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(RE int i=h[u];i;i=net[i]){
            e[++cnt].u=u,e[cnt].v=to[i],e[cnt].w=w[i];
            if(!vis[to[i]]) vis[to[i]]=1,tot++,q.push(to[i]);
        }
    }
}

il void init(){
    n=gi(),m=gi();
    For(i,1,n) fa[i]=i,H[i]=gi();
    int u,v,c;
    For(i,1,m) {
        u=gi(),v=gi(),c=gi();
        if(H[u]>=H[v]) add(u,v,c);
        if(H[u]<=H[v]) add(v,u,c);
    }
    cnt=0,bfs();
    sort(e+1,e+cnt+1);
    ll ans=0;
    For(i,1,cnt) {
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v) fa[u]=v,ans+=e[i].w;
    }
    cout<<tot+1<<' '<<ans;
}

int main(){
    init();
    return 0;
}