Home > OI > NOI 2006 最大获利

NOI 2006 最大获利


最大权闭合图。可参考胡伯涛的论文。该题的标准解法是贪心初始流+最大流。但用SAP+GAP+当前弧优化可以秒过。

早就听说当前弧优化,但是一加到自己代码上就错。这次终于找到原因了,因为以前把更新距离标号的一部分操作挪到寻找可行弧时完成,但这样一来就会出现问题。把操作独立出来之后问题就解决了。

#include<stdio.h> #include<string.h> #define MAXN 70001 #define MAXE 400001 #define oo 0x77777777 struct Edge{     int v,w;     Edge *next,*pair; } *edge[MAXN],mempool[MAXE],*cur[MAXN]; int S,T,counter[MAXN],layer[MAXN],minf,found,ans,memnum; inline int min(int a, int b){     return a<b?a:b; } void add(int s, int t, int w){     Edge *x=&mempool[memnum++],*y=&mempool[memnum++];     x->v=t,x->w=w,x->pair=y,x->next=edge[s],edge[s]=x;     y->v=s,y->w=0,y->pair=x,y->next=edge[t],edge[t]=y; } void aug(int now){     if(now==T){         found=1;         ans+=minf;         return;     }     Edge *i;     int tmp=minf;     for(i=cur[now];i;i=i->next){         if(i->w>0){             if(layer[now]==layer[i->v]+1){                 cur[now]=i;                 minf=min(minf,i->w);                 aug(i->v);                 if(layer[S]>T) return;                 if(found) break;                 minf=tmp;             }         }     }     if(!found){         int minl=T;         for(i=cur[now]=edge[now];i;i=i->next) if(i->w>0) minl=min(minl,layer[i->v]);         if(!(--counter[layer[now]])) layer[S]=T+1;         ++counter[layer[now]=minl+1];     }else{         i->w-=minf;         i->pair->w+=minf;     } } void sap(){     memset(counter,0,sizeof(counter));     memset(layer,0,sizeof(layer));     counter[0]=T+1;     memcpy(cur,edge,sizeof(edge));     while(layer[S]<=T){         found=0;         minf=oo;         aug(S);     } } int main(){     freopen("1.in","r",stdin);     freopen("1.out","w",stdout);     int sum=0,a,b,c,x,N,M;     scanf("%d %d\n",&N,&M);     S=0,T=N+M+1;     for(int i=1;i<=N;++i){         scanf("%d",&x);         add(i,T,x);     }     for(int i=1;i<=M;++i){         scanf("%d %d %d\n",&a,&b,&c);         add(i+N,a,oo);         add(i+N,b,oo);         add(S,i+N,c);         sum+=c;     }     sap();     printf("%d\n",sum-ans);     return 0; }
Categories: OI Tags: , , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: