【BZOJ2753】【SCOI2012】滑雪与时间胶囊

第一问BFS一下就没了

第二问就是对第一问中的点跑个最小树形图

因为连边很有规律，所以可以从高到低每次将一部分点加入图中。具体就是将边以较低点高度为第一关键字倒序，边权为第二关键字升序排序跑Kruskal。

// <2753.cpp> - Sat Mar 11 20:49:56 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
#define next NEXT
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=100010;
const int MAXM=2000010;
const int INF=1e9;
int h[MAXN];
struct edge{
    int u,v,w;
    bool operator <(const edge b) const{return h[v]==h[b.v]?w<b.w:h[v]>h[b.v];}
}e[MAXM];
int bt,b[MAXN],next[MAXM],to[MAXM];
inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;}
queue <int> q;
bool vis[MAXN];
int f[MAXN];
int gf(int x){if(f[x]!=f[f[x]])f[x]=gf(f[x]);return f[x];}
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=n;i++)h[i]=gi(),f[i]=i;
    for(int i=1;i<=m;i++){
        e[i].u=gi(),e[i].v=gi(),e[i].w=gi();
        if(h[e[i].u]<h[e[i].v])swap(e[i].u,e[i].v);
        add(e[i].u,e[i].v);
        if(h[e[i].u]==h[e[i].v])add(e[i].v,e[i].u);
    }
    q.push(1);vis[1]=1;
    int cnt=1;lol ans=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=b[x];i;i=next[i]){
            if(vis[to[i]])continue;
            vis[to[i]]=1;cnt++;
            q.push(to[i]);
        }
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        int fa=gf(e[i].u),fb=gf(e[i].v);
        if(fa==fb||!vis[fa]||!vis[fb])continue;
        f[fa]=fb;
        ans+=e[i].w;
    }
    printf("%d %lld",cnt,ans);
    return 0;
}

// <2753.cpp> - Sat Mar 11 20:49:56 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

#define next NEXT

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=100010;

const int MAXM=2000010;

const int INF=1e9;

int h[MAXN];

struct edge{

int u,v,w;

bool operator <(const edge b) const{return h[v]==h[b.v]?w<b.w:h[v]>h[b.v];}

}e[MAXM];

int bt,b[MAXN],next[MAXM],to[MAXM];

inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;}

queue <int> q;

bool vis[MAXN];

int f[MAXN];

int gf(int x){if(f[x]!=f[f[x]])f[x]=gf(f[x]);return f[x];}

int main(){

int n=gi(),m=gi();

for(int i=1;i<=n;i++)h[i]=gi(),f[i]=i;

for(int i=1;i<=m;i++){

e[i].u=gi(),e[i].v=gi(),e[i].w=gi();

if(h[e[i].u]<h[e[i].v])swap(e[i].u,e[i].v);

add(e[i].u,e[i].v);

if(h[e[i].u]==h[e[i].v])add(e[i].v,e[i].u);

}

q.push(1);vis[1]=1;

int cnt=1;lol ans=0;

while(!q.empty()){

int x=q.front();q.pop();

for(int i=b[x];i;i=next[i]){

if(vis[to[i]])continue;

vis[to[i]]=1;cnt++;

q.push(to[i]);

}

sort(e+1,e+m+1);

for(int i=1;i<=m;i++){

int fa=gf(e[i].u),fb=gf(e[i].v);

if(fa==fb||!vis[fa]||!vis[fb])continue;

f[fa]=fb;

ans+=e[i].w;

}

printf("%d %lld",cnt,ans);

return 0;

}