P2573滑雪题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-07-03 15:59:26

这道题需要注意的是，数据范围太阴间，需要开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;
}

vector 的博客

博客

评论

发表评论

__vector__ 的博客

博客