Archive

Posts Tagged ‘NOI’

NOI 2008 志愿者招募

July 28, 2010 Leave a comment

这题竟然在省赛第3天中出现,要是当时有多做点NOI原题就好了

以样例来分析,设X[i]为第i类志愿者的人数,那么可得到约束为

Day[1]=X[1]>=2

Day[2]=X[1]+X[2]>=3

Day[3]=X[2]+X[3]>=4

添加辅助变量Y,将其化为等式得

Day'[1]=X[1]-Y[1]=2

Day'[2]=X[1]+X[2]-Y[2]=3

Day'[3]=X[2]+X[3]-Y[3]=4

添加第0、第4个等式,相邻等式两两相减(下减上)得

P[1]=X[1]-Y[1]=2

P[2]=X[2]+Y[1]-Y[2]=1

P[3]=X[3]+Y[2]-X[1]-Y[3]=1

P[4]=Y[3]-X[2]-X[3]=-4

进一步转化等式得

2-X[1]+Y[1]=0

1-X[2]-Y[1]+Y[2]=0

1-X[3]-Y[2]+X[1]+Y[3]=0

-4-Y[3]+X[2]+X[3]=0

分析上面四个等式,每个X[i]、Y[i]一正一负恰出现一次,若以每个等式为网络流中的顶点,上式就是流量守恒的形式

现规定以正为入,负为出,则对于每个P[i]:

若右端常数为正,从源点向该等式连边,容量为常数值,费用为0

若右端常数为负,从该等式向汇点连边,容量为常数值绝对值,费用为0

对于每个X[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为C[i]

对于每个Y[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为0

求最小费用最大流即为答案

#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 20001 #define QMAX 20001 #define MAXE 100001 #define oo 0x77777777 struct Edge{     int v,w,p;     Edge *next,*pair; } *edge[MAXN],*fe[MAXN],mempool[MAXE]; int S,T,memnum,dis[MAXN],Que[MAXN],vis[MAXN], Closed,Open,Size,ft[MAXN],ans; inline int min(int a, int b){     return a<b?a:b; } void add(int s, int t, int w, int p){     Edge *x=&mempool[memnum++],*y=&mempool[memnum++];     x->v=t,x->w=w,x->p=p,x->next=edge[s],x->pair=y,edge[s]=x;     y->v=s,y->w=0,y->p=-p,y->next=edge[t],y->pair=x,edge[t]=y; } int spfa(){     memset(dis,0x77,sizeof(dis));     memset(vis,0,sizeof(vis));     memset(ft,0,sizeof(ft));     memset(fe,0,sizeof(fe));     Closed=0,Open=0,Size=1,Que[0]=S,vis[S]=1,dis[S]=0;     while(Size){         int now=Que[Closed];         vis[now]=0,--Size,Closed=(Closed+1)%QMAX;         for(Edge *tmp=edge[now];tmp;tmp=tmp->next){             if(tmp->w>0){                 if(dis[now]+tmp->p<dis[tmp->v]){                     dis[tmp->v]=dis[now]+tmp->p;                     ft[tmp->v]=now;                     fe[tmp->v]=tmp;                     if(!vis[tmp->v]){                         ++Size;                         vis[tmp->v]=1;                         if(!Size||dis[tmp->v]<dis[Que[Closed]]){                             Closed=(Closed-1+QMAX)%QMAX;                             Que[Closed]=tmp->v;                         }else{                             Open=(Open+1)%QMAX;                             Que[Open]=tmp->v;                         }                     }                 }             }         }     }     return dis[T]<oo; } void aug(){     int delta=oo;     for(int i=T;i!=S;i=ft[i]){         if(fe[i]->w<delta){             delta=fe[i]->w;         }     }     for(int i=T;i!=S;i=ft[i]){         fe[i]->w-=delta,fe[i]->pair->w+=delta,ans+=delta*fe[i]->p;     } } int main(){     int N,M,x,y=0,s,t,c;     freopen("1.in","r",stdin);     freopen("1.out","w",stdout);     scanf("%d%d",&N,&M);     S=0,T=N+2;     for(int i=1;i<=N;++i){         scanf("%d",&x);         t=x-y;         if(t>0){             add(S,i,t,0);         }else{             add(i,T,-t,0);         }         y=x;         add(i+1,i,oo,0);     }     add(N+1,T,x,0);     for(int i=1;i<=M;++i){         scanf("%d%d%d",&s,&t,&c);         add(s,min(N+1,t+1),oo,c);     }     while(spfa())         aug();     printf("%d\n",ans);     return 0; }
Categories: OI Tags: , , , ,

NOI 2006 最大获利

July 28, 2010 Leave a comment

最大权闭合图。可参考胡伯涛的论文。该题的标准解法是贪心初始流+最大流。但用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: , , , ,