2151: 种树

Description

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

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

输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出“Error!”，不包含引号。
Sample Input
【样例输入1】
7 3
1 2 3 4 5 6 7
【样例输入2】
7 4
1 2 3 4 5 6 7

Sample Output
【样例输出1】
15

【样例输出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

看wikioi的题解完全没有看懂

于是问了群里的人，结果告诉我是费用流优化

搞了半天总算懂了

首先我们把它拆成链，因为这样我们就好做了，我们只要算两遍就行了，一个是[1,n-1](表示n不取)一个是[2,n](表示1不取)

然后构费用流的图（有点奇葩......）

然后跑费用流就行了

但是显然不能跑费用流，承受不了

所以我们模拟费用流

假设我们选了点2（因为费用最大），然后增广后，残留网络是这样的

第1，2，3条路都没了

但是我们可以走从1到2到3，即多了一条路，费用为a[1]+a[3]-a[2]

我们也可以分析出只多出了这条路，其他的路都是没有用的

因为a[2]>=a[1]，所以我们不可能从1走到2再走到S，所以没有别的路了

所以对于这种情况我们就用a[pre[i]]+a[next[i]]-a[i]代替a[i],然后删除pre[i]和next[i]

还有一种情况就是i是两端

这种情况想一想就知道了，端点是最大的那么就选端点，然后删掉在端点的那两个值就行了

所以我们用堆维护最大值，做m次就行了

 const

     maxn=;

 var

     q,h,a,b,pre,next:array[..maxn]of longint;

     n,m,tot:longint;

 function max(x,y:longint):longint;

 begin

     if x>y then exit(x);

     exit(y);

 end;

 procedure swap(var x,y:longint);

 var

     t:longint;

 begin

     t:=x;x:=y;y:=t;

 end;

 procedure up(x:longint);

 var

     i:longint;

 begin

     while x> do

       begin

         i:=x>>;

         if b[q[x]]>b[q[i]] then

           begin

             swap(q[x],q[i]);

             h[q[x]]:=x;

             h[q[i]]:=i;

             x:=i;

           end

         else break;

       end;

 end;

 procedure down(x:longint);

 var

     i:longint;

 begin

     i:=x<<;

     while i<=tot do

       begin

         if (i<tot) and (b[q[i+]]>b[q[i]]) then inc(i);

         if b[q[i]]>b[q[x]] then

           begin

             swap(q[x],q[i]);

             h[q[x]]:=x;

             h[q[i]]:=i;

             x:=i;

             i:=x<<;

           end

         else break;

       end;

 end;

 procedure insert(x:longint);

 begin

     inc(tot);

     h[x]:=tot;

     q[tot]:=x;

     up(tot);

 end;

 procedure delete(x:longint);

 begin

     if x= then exit;

     b[q[x]]:=maxlongint;

     up(x);

     swap(q[],q[tot]);

     h[q[]]:=;

     h[q[tot]]:=tot;

     dec(tot);

     down();

 end;

 function f(l,r:longint):longint;

 var

     i,u,v,t:longint;

 begin

     f:=;

     tot:=;

     for i:=l to r do

       begin

         b[i]:=a[i];

         insert(i);

         pre[i]:=i-;

         next[i]:=i+;

       end;

     pre[l]:=;

     next[r]:=;

     for i:= to m do

       begin

         t:=q[];

         inc(f,b[t]);

         u:=pre[t];

         v:=next[t];

         if (u<>) and (v<>) then

           begin

             b[t]:=b[u]+b[v]-b[t];

             pre[t]:=pre[u];

             next[t]:=next[v];

             next[pre[t]]:=t;

             pre[next[t]]:=t;

             down(h[t]);

           end

         else

           begin

             if u<> then next[pre[u]]:=;

             if v<> then pre[next[v]]:=;

             delete(h[t]);

           end;

         delete(h[u]);

         delete(h[v]);

       end;

 end;

 procedure main;

 var

     i:longint;

 begin

     read(n,m);

     if m*>n then

     begin

       writeln('Error!');

       exit;

     end;

     for i:= to n do

       read(a[i]);

     writeln(max(f(,n-),f(,n)));

 end;

 begin

     main;

 end.

巴特西

2151: 种树 - BZOJ

最新文章

热门文章