[APIO2007 backup]用贪心实现特殊图的费用流增广**

【题目】http://www.oi.bbjy.com/n38c10.aspx

【算法分析】

O(nk)的dp。测得70分….

然后我YY到一个费用流，发现复杂度还是O(nk)，而且常数上必然比dp更慢。。。

于是翻看Sinya神牛的题解。。。Orz，原来是用贪心去做费用流。。。彻底膜拜。

http://sinyalee.com/blog/?p=427

拜一下先….

然后我YY到的费用流就和野牛的建图一样.

下面我就说一下我对那个贪心的理解.

首先我们想象我们是一只小蝌蚪,在流中寻找增广路….

(借一下野牛的图。。。)

然后可以YY到，我们找的增广路必然是从与S相连的一条未增广的边进去，然后向左或者向右若干次“上下波动”（当然也可以不上下动，直接进去T那里），然后跑到T点去。

如在a2->a3->a4这里波动。

我们如果增广路包含这一路径的话，就可以看成把a3给取消了，然后选择了a2和a4.
这样的话，连续的(不取，取，不取，取，不取….)就可以当成一个组。

注意最左边和最右边都必须为“不取”。

分成那个组以后，组的中间必然是不能做增广的，因为与S相连的边已经饱和~

所以就可以看成必须在两端搞进去。。。搞了以后，无论在左边开始搞还是右边开始搞，结果都是一样的，都是多了一个点，都是向两边迈进了一步。（画图YY一下即可）

然后就再把相邻的两组合并到一起。因为你和她已经弄成新的OXOXOXOXOXOXO….结构了

现在大体我们已经明了了，但是边沿情况怎么处理呢？

注意到，如果a1或者an已经选了，是不可能再取消的。那就别放进决策队列。

证明：

你YY一下费用流的增广过程，

会发现那里要么和S连的只属于一个点的边已经满流，要么和T连的只属于一个店的边已经满流，你是没有办法取消它了。。。

因为费用流是对的，所以这个是对的，因为这只是在模拟增广费用流。

然后综上一下，发现堆可以达到我们需要的每次找最短增广路径的目的。

增广增加的费用其实就是SUM[L[i],R[i]]-2*w[i]。

其中sum[i,j]表示a[i]到a[j]的和，w[i]表示这个区间已经选了的点的权值和。

根据这个做堆的关键字就可以了。

【其他】膜拜Sinya

【CODE】

#include #include #include #include using namespace std;
const int N=101111;
int n,K;
int a[N],inheap[N],fa[N],L[N],R[N];
int sum[N],ans;

inline int S(int i,int j){
       if (!i) return sum[j];
       return sum[j]-sum[i-1];
}

struct HeapType{
       struct pt{int pos;int w;}h[N];
       int tot;
      
       bool cmp(int i,int j){
            return (S(L[h[i].pos],R[h[i].pos])-h[i].w*2)
                  <(S(L[h[j].pos],R[h[j].pos])-h[j].w*2);
       }
      
       void swap(int i,int j){
            int tmp;
            tmp=h[i].pos; h[i].pos=h[j].pos; h[j].pos=tmp;
            tmp=h[i].w; h[i].w=h[j].w; h[j].w=tmp;
            inheap[h[i].pos]=i; inheap[h[j].pos]=j;
       }
      
       void up(int k){
            while (k>1 && cmp(k,k/2)){
                  swap(k/2,k);
                  k/=2;
            }
       }
      
       void down(int k){
            int p;
            while (k*2<=tot){
                  p=k*2;
                  if (p+1<=tot && cmp(p+1,p)) p++;
                  if (cmp(p,k)){
                    swap(p,k);
                    k=p;
                  }else break;
            }
       }
      
       void ins(int pos,int w){
            tot++;
            h[tot].pos=pos;
            h[tot].w=w;
            inheap[pos]=tot;
            up(tot);    
       }
      
       void del(int inh){
            if (!inh) return;
            int tmp=h[inh].pos;
            swap(tot,inh);
            inheap[tmp]=0;
            tot–;
            up(inh);
            down(inh);
       }
}heap;

void input(){
     cin >> n >> K;
     int x;
     for (int i=1;i<=n;i++){
         scanf("%d",&x);
         a[i]=x;
     }
     for (int i=1;i     n–;
     sum[0]=0;
     for (int i=1;i<=n+1;i++){
         L[i]=i; R[i]=i; fa[i]=i;
         sum[i]=sum[i-1]+a[i];
     }
     L[0]=0; R[0]=0; fa[0]=0;
     heap.tot=0;
     for (int i=1;i<=n;i++) heap.ins(i,0);
}

int gf(int k){
    if (fa[k]==k) return k;
    fa[k]=gf(fa[k]);
    return fa[k];
}

void work(){    
     int i,k,ans=0,Lc,Rc,p,nw;
     for (k=1;k<=K;k++){
         p=gf(heap.h[1].pos);
         ans+=S(L[p],R[p])-heap.h[1].w*2;
         nw=S(L[p],R[p])-heap.h[1].w;
         heap.del(1);
        
         Lc=gf(L[p]-1);
         nw+=heap.h[inheap[Lc]].w;
         L[p]=L[Lc];
         fa[Lc]=p;
         heap.del(inheap[Lc]);
        
         Rc=gf(R[p]+1);
         nw+=heap.h[inheap[Rc]].w;
         R[p]=R[Rc];
         fa[Rc]=p;
         heap.del(inheap[Rc]);
        
         if (L[p]>0 && R[p]<=n) heap.ins(p,nw);
     }
     cout << ans << endl;
}

int main(){
    freopen("backup.in","r",stdin);
    freopen("backup.out","w",stdout);
    input();
    work();
    return 0;
}