[BZOJ2753][SCOI2012]滑雪与时间胶囊 最小生成树


原题链接
给一张边权图,每个点有高度,每个点只能朝不比它高的点走,且走过的点可以瞬间传送回去,问从1号店开始能遍历多少点,以及最小耗时.
第一问就是个BFS,第二问实际上是求最小树形图,但朱刘算法复杂度不允许,而直接kruskal又不对,怎么办呢?
考虑kruskal的反例:
4 4
3 2 2 1
1 2 2
1 3 2
2 4 1
3 4 1
按照kruskal的思路,肯定会将两条连向4的边都选中,然而这样是错误的.错误的原因就是,两个点不能通过比它们低的点连接.为了避免这种情况发生,我们需要将图分层,把边按照结束节点高度为第一关键字,边权为第二关键字排序即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
#define M 2002333
using namespace std;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
typedef long long ll;
int n,m,head[N],tot;
struct Node
{
    int x,y,z,nxt;
}e[M];
inline void add(int x,int y,int z)
{
    e[++tot].x=x,e[tot].y=y,e[tot].z=z;
    e[tot].nxt=head[x];head[x]=tot;
}
int h[N],vis[N],q[N],l=1,r;
void bfs()
{
    int x,i,y;
    vis[1]=1,q[++r]=1;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=e[i].nxt)
            if(!vis[e[i].y])q[++r]=e[i].y,vis[e[i].y]=1;
    }
}
inline bool cmp(const Node a,const Node b)
{
    return h[a.y]>h[b.y]||(h[a.y]==h[b.y]&&a.z<b.z);
}
int fa[N];
inline void init()
{
    for(int i=1;i<=n;++i)fa[i]=i;
}
int find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline int merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return 0;
    fa[x]=y;return 1;
}
ll ans;
int main()
{
    read(n),read(m);
    int i,x,y,z;
    for(i=1;i<=n;++i)read(h[i]);
    for(i=1;i<=m;++i)
    {
        read(x),read(y),read(z);
        if(h[x]>=h[y])add(x,y,z);
        if(h[y]>=h[x])add(y,x,z);
    }
    bfs();
    sort(e+1,e+tot+1,cmp);
    init();
    for(i=1;i<=tot;++i)if(vis[x=e[i].x]&&vis[y=e[i].y])
    {
        if(merge(x,y))ans+=e[i].z;
    }
    printf("%d %lld\n",r,ans);
    return 0;
}

《[BZOJ2753][SCOI2012]滑雪与时间胶囊 最小生成树》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注