第一问BFS一下就没了
第二问就是对第一问中的点跑个最小树形图
因为连边很有规律，所以可以从高到低每次将一部分点加入图中。具体就是将边以较低点高度为第一关键字倒序，边权为第二关键字升序排序跑Kruskal。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// <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; } |
说点什么