P2573 [SCOI2012]滑雪

短命女 2023-06-04 07:58 114阅读 0赞

[题目链接][Link 1]

**在题中每个点都有一个限制条件，对于一个点，只能通向高度低于它的点，所以我们可以对题目中的所有点建有向图。然后可以从1开始通过bfs找到所有可以通向的点。**

**找到了这些点过后又怎么办呢？题目中说要使得经过最多景点数的点的边权值最小。所以我们能够在bfs的同时将这些能够到达的点都建一个新的图。然后从1开始在这个新图上跑；kruskal即可求出最小的权值。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int nxt,to,val;
    }edge[maxn*3];
    int dis[maxn];
    int head[maxn],cnt;
    void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    int n,m,x,y,v;
    int h[maxn];
    bool vis[maxn];
    int sum;
    queue<int> q;
    struct node2{
        int x,y,val;
    }tree[maxn*3];
    int tot;
    int fa[maxn];
    int get(int x){
        if(x==fa[x]) return x;
        return fa[x]=get(fa[x]);
    }
    void bfs(){
        memset(vis,false,sizeof(vis));
        q.push(1);
        vis[1]=true;
        sum=1;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u];i;i=edge[i].nxt){
                int v=edge[i].to;
                tree[++tot].x=u;
                tree[tot].y=v;
                tree[tot].val=edge[i].val;
                if(!vis[v]){
                    vis[v]=true;
                    sum++;
                    q.push(v);
                }
            }
        }
    }
    bool cmp(node2 a,node2 b){
        if(h[a.y]!=h[b.y]) return h[a.y]>h[b.y]; 
        else return a.val<b.val;
    }
    long long all;
    void kruskal(){
        int ans=0;
        sort(tree+1,tree+1+tot,cmp);
        for(int i=1;i<=tot;i++){
            int f1=get(tree[i].x);
            int f2=get(tree[i].y);
            if(f1!=f2){
                fa[f1]=f2;
                ans++;
                all+=tree[i].val;
                if(ans==sum-1) break;
            }
        }
        printf("%d %lld\n",sum,all);
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=n;i++) scanf("%d",&h[i]);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&v);
            if(h[x]>=h[y]) add(x,y,v);
            if(h[x]<=h[y]) add(y,x,v);
        }
        bfs();
        kruskal();
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11623715.html

[Link 1]: https://www.luogu.org/problem/P2573
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/ec07037b20744e0b81f689e83342d290.png