Home > OI > NOI 2008 志愿者招募

NOI 2008 志愿者招募


这题竟然在省赛第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: , , , ,
  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: