BZOJ2151种树——模拟费用流+链表+堆-白红宇

BZOJ2151种树——模拟费用流+链表+堆

阅读量：6811 次

发布时间：2019-06-26

本文共 1724 字，大约阅读时间需要 5 分钟。

题目描述

A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。最终市政府给园林部门提供了m棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上，给出无解信息。

输入

输入的第一行包含两个正整数n、m。第二行n个整数Ai。

输出

输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出“Error!”，不包含引号。

样例输入

【样例输入1】

7 3

1 2 3 4 5 6 7

【样例输入2】

7 4

1 2 3 4 5 6 7

样例输出

【样例输出1】

【样例输出2】

Error!

【数据规模】

对于全部数据：m<=n；

-1000<=Ai<=1000

N的大小对于不同数据有所不同：

数据编号 N的大小数据编号 N的大小

1 30 11 200

2 35 12 2007

3 40 13 2008

4 45 14 2009

5 50 15 2010

6 55 16 2011

7 60 17 2012

8 65 18 199999

9 200 19 199999

10 200 20 200000

方法同，只需要将两端连起来即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;priority_queue
              
               
                 >q;int n,m;int x;int vis[400010];int cnt;struct node{ int num; int sum; int pre; int suf;}a[400010];map
                
                 b;int ans;int main(){ scanf("%d%d",&n,&m); if(m*2>n) { printf("Error!"); return 0; } for(int i=1;i<=n;i++) { scanf("%d",&x); a[++cnt].num=i; a[cnt].sum=x; if(i!=n) { a[cnt].suf=i+1; } else { a[cnt].suf=1; } if(i!=1) { a[cnt].pre=i-1; } else { a[cnt].pre=n; } q.push(make_pair(a[cnt].sum,a[cnt].num)); } while(m!=0) { int y=q.top().first; int z=q.top().second; q.pop(); if(!vis[z]) { ans+=y; vis[z]=1; vis[a[z].pre]=1; vis[a[z].suf]=1; a[++cnt].sum=a[a[z].pre].sum+a[a[z].suf].sum-y; a[cnt].num=cnt; a[cnt].pre=a[a[z].pre].pre; a[cnt].suf=a[a[z].suf].suf; a[a[a[z].pre].pre].suf=cnt; a[a[a[z].suf].suf].pre=cnt; q.push(make_pair(a[cnt].sum,a[cnt].num)); m--; } } printf("%d",ans);}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10421591.html

你可能感兴趣的文章