[SCOI2012]滑雪 题解
[SCOI2012]滑雪
问：景点数最大的同时 滑行总距离最小
景点数最大 即求 最大连通块
滑行总距离最小 即求 最小生成树
对于多条件问题 有限考虑硬性条件（可行性） 再考虑最优性
1.可行性
滑行必须从高到低（相等也可），即更新节点时必然是从高的点更新低的点，
所以选择节点时 优 先 考虑高的节点
结论 对所有节点从高到低排序
2.最优性
与最小生成树同理
优先选择长度最短的边
结论 对所有边从小到大排序
3.坑点
- 当两个点高度相等是，是双向边
- 既然是双向边，就要开两倍数组，否则RE
- 只考虑了最优性而没有考虑可行性
4.代码如下
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const ll N = 1e5+7, M = 2 * 1e6+7, INF = 5e9+9; // 可能存在双向边
ll n,m,h[N];
ll head[N],tot;
struct edge
{
ll ver,dis,nex;
}e[M],pe[M];
void add(ll u,ll v,ll w)
{
e[++tot].nex = head[u];
e[tot].ver = v;
e[tot].dis = w;
head[u] = tot;
}
ll phead[N],ptot;
void padd(ll u,ll v,ll w)
{
pe[++ptot].nex = phead[u];
pe[ptot].ver = v;
pe[ptot].dis = w;
phead[u] = ptot;
}
bool arr[N];
ll num;
void bfs(ll begin)
{
queue<ll> q;
arr[begin] = 1;
num++;
q.push(begin);
while(q.size())
{
ll now = q.front();
q.pop();
for(ll i=head[now];i;i=e[i].nex)
{
padd(now,e[i].ver,e[i].dis);
if(arr[e[i].ver])continue;
arr[e[i].ver] = 1;
num++;
q.push(e[i].ver);
}
}
}
struct cmp
{
bool operator()(edge a,edge b)
{
if(h[a.ver]!=h[b.ver])return h[a.ver] < h[b.ver];//可行性
return a.dis>b.dis;//最优性
}
};
ll dis[N],sum;
void prim(ll begin)
{
priority_queue< edge , vector<edge> , cmp > q;
for(ll i=1;i<=n;i++)dis[i]=INF;
dis[begin] = 0;
for(ll i=phead[begin];i;i=pe[i].nex)
{
if(dis[begin] + pe[i].dis < dis[pe[i].ver])
{
q.push(pe[i]);
dis[pe[i].ver]=pe[i].dis;
}
}
while(q.size())
{
edge now = q.top();
q.pop();
if(!dis[now.ver])continue;
dis[now.ver]=0;
sum+=now.dis;
for(ll i=phead[now.ver];i;i=pe[i].nex)
{
if(dis[begin] + pe[i].dis < dis[pe[i].ver])
{
dis[pe[i].ver] = pe[i].dis;
q.push(pe[i]);
}
}
}
}
int main()
{
n = read();
m = read();
for(ll i=1;i<=n;i++)h[i]=read();
for(ll i=1;i<=m;i++)
{
ll u,v,w;
u=read();
v=read();
w=read();
if(h[u]<=h[v])add(v,u,w);
if(h[u]>=h[v])add(u,v,w);
}
bfs(1);//事实上不需要BFS
prim(1);
printf("%lld %lld",num,sum);
return 0;
}