P2573滑雪题解
__vector__ · · 个人记录
这道题需要注意的是，数据范围太阴间，需要开long long才行，数值范围也要搞好。
#define maxn 100002
#define maxm 2000002
typedef long long ll;这道题可以用广搜+最小生成树+并查集快速解决。其中要使用结构体存图，赋值给两个数组，一个用于存储原始数据，另一个用于存储BFS处理后的数据
struct EDGE//重温邻接表
{
ll u,v,w,next;
}edge[maxm],edge_fb[maxm];
最初图输入时，因为只能从一个点 到更低或一样高的点，所以加一个判断，如果头点edge[i].u 大于或等于尾点edge[i].to那么建立从edge[i].u 到 edge[i].to的边，然后再判断（千万不要加else，直接判断，我在这里挂了好几个测试点），如果尾点edge[i].to 大于或等于头点edge[i].u那么建立从edge[i].to 到edge[i].u的边。
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> h[i];
}
for(int i = 1;i <= n;i++)
{
f[i]=i;
}
for(int i = 1; i<= m;i++)
{
int u,v,w;
cin >> u >> v >> w;
if(h[u] >= h[v])add_edge(u,v,w);
if(h[u] <= h[v]) add_edge(v,u,w);//只能是从高的往低的建边
}然后要枚举每一个能走到的点和边，并存入第二个结构体数组，这就要用到搜索了，既可以用广搜也可以用深搜，本蒟蒻只能用广搜来AC，深搜暂时只有80分，所以就使用广搜了。
inline void bfs(ll u)//BFS函数，谁都应该会吧
{
q.push(u);
vis[u]=1;
while(!q.empty())
{
int tmp = q.front();//存储状态
q.pop();
for(int i = head[tmp];i != 0;i = edge[i].next)
{
edge_fb[++edge_sum].u=tmp;//保存状态
edge_fb[edge_sum].v = edge[i].v;
edge_fb[edge_sum].w = edge[i].w;
int tmp2 = edge[i].v;
if(!vis[tmp2])//如果没遍历这个点
{
q.push(tmp2);
node_sum++;
vis[tmp2]=1;
}
}
}
}然后要对BFS处理后的数据进行一波排序，要将边的长度从小到大排，将高度从高到低排，因为kruskal尽量求最小值，按顺序来依次枚举，逐渐增大，才能保证数据最小，所以从小到大排。而只能从高到低，所以从高到低排。
ll cmp(EDGE a,EDGE b)
{
return h[a.v]!=h[b.v]?h[a.v]>h[b.v]:a.w<b.w;
}
sort(edge_fb+1,edge_fb+edge_sum+1,cmp);
然后就是最小生成树kruskal+并查集（本蒟蒻只会kruskal），这个就不用说了，神仙们一定都会
inline void kruscal()
{
for(int i = 1;i <= edge_sum;i++)
{
int xx = find(edge_fb[i].u);
int yy = find(edge_fb[i].v);
if(xx!=yy)
{
//cout << "ok: " << edge_fb[i].w << endl;
f[xx]=yy;
ans+=edge_fb[i].w;
}
}
}下面附上完整代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<utility>
#include<deque>
#include<ctime>
#include<sstream>
#include<list>
#include<bitset>
using namespace std;
#define maxn 100002
#define maxm 2000002
typedef long long ll;
ll n,m,f[maxn],h[maxn],cnt,head[maxn],edge_sum,node_sum=1,ans;
bool vis[maxn];
queue<int> q;
struct EDGE//重温邻接表(有向图)
{
ll u,v,w,next;
}edge[maxm],edge_fb[maxm];
void add_edge(int u,int v,int w)//普通的加边函数
{
edge[++cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u]=cnt;
}
inline void bfs(ll u)//BFS函数，谁都应该会吧
{
q.push(u);
vis[u]=1;
while(!q.empty())
{
int tmp = q.front();//存储状态
q.pop();
for(int i = head[tmp];i != 0;i = edge[i].next)
{
edge_fb[++edge_sum].u=tmp;//保存状态
edge_fb[edge_sum].v = edge[i].v;
edge_fb[edge_sum].w = edge[i].w;
int tmp2 = edge[i].v;
if(!vis[tmp2])//如果没遍历这个点
{
q.push(tmp2);
node_sum++;
vis[tmp2]=1;
}
}
}
}
ll cmp(EDGE a,EDGE b)
{
return h[a.v]!=h[b.v]?h[a.v]>h[b.v]:a.w<b.w;
}//要将高度从高到低排列，长度从短到长排列，方便最小生成树
ll find(int to)
{
return f[to]==to?to:f[to]=find(f[to]);
}
inline void kruscal()
{
for(int i = 1;i <= edge_sum;i++)
{
int xx = find(edge_fb[i].u);
int yy = find(edge_fb[i].v);
if(xx!=yy)
{
//cout << "ok: " << edge_fb[i].w << endl;
f[xx]=yy;
ans+=edge_fb[i].w;
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> h[i];
}
for(int i = 1;i <= n;i++)
{
f[i]=i;
}
for(int i = 1; i<= m;i++)
{
int u,v,w;
cin >> u >> v >> w;
if(h[u] >= h[v])add_edge(u,v,w);
if(h[u] <= h[v]) add_edge(v,u,w);//只能是从高的往低的建边
}
bfs(1);//所有能搜到的点就是最多能到达点数
sort(edge_fb+1,edge_fb+edge_sum+1,cmp);
kruscal();
cout << node_sum << " " << ans << endl;
return 0;
}