洛谷P3980：[NOI2008]志愿者招募-白红宇

洛谷P3980：[NOI2008]志愿者招募

阅读量：5008 次

发布时间：2019-06-12

本文共 4628 字，大约阅读时间需要 15 分钟。

线性规划：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #define rint register int 8 #define ll long long 9 #define MAXN 1000+10 10 #define pb push_back 11 #define INF 0x7f7f7f7f 12 #define oo 0x7f7f7f7f7f7f7f7f 13 #define pil pair
           
             14 #define mp make_pair 15 using namespace std; 16 int read(){ 17 int x=0,f=1;char ch=getchar(); 18 while(ch<'0'||ch>'9'){ if('-'==ch)f=-1;ch=getchar();} 19 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 struct E{ 23 int from,to,cap,flow; 24 ll cost; 25 E(int x=0,int y=0,int c=0,int f=0,ll w=0LL){ 26 from=x,to=y,cap=c,flow=f,cost=w; 27 } 28 }; 29 struct Dinic{ 30 int n,m,s,t; 31 vector
            
              es; 32 vector
             
               G[MAXN]; 33 void init(int n,int s,int t){ 34 this->n=n; 35 this->s=s,this->t=t; 36 es.clear(); 37 for(int i=0;i<=n;i++)G[i].clear(); 38 } 39 void add(int x,int y,int cap,ll cost){ 40 es.pb(E(x,y,cap,0,cost)); 41 es.pb(E(y,x,0,0,-cost)); 42 m=es.size(); 43 G[x].pb(m-2),G[y].pb(m-1); 44 } 45 int p[MAXN],a[MAXN]; 46 ll d[MAXN]; 47 int b[MAXN]; 48 bool SPFA(int &flow,ll &cost){ 49 p[s]=0,a[s]=INF; 50 memset(d,0x7f,sizeof(d)); 51 d[s]=0; 52 memset(b,0,sizeof(b)); 53 b[s]=1; 54 queue
              
                q; 55 q.push(s); 56 while(!q.empty()){ 57 int x=q.front();q.pop();b[x]=0; 58 for(rint i=0;i
               
                e.flow&&d[e.to]>d[x]+e.cost){ 61 p[e.to]=G[x][i]; 62 a[e.to]=min(a[x],e.cap-e.flow); 63 d[e.to]=d[x]+e.cost; 64 if(!b[e.to]){ 65 b[e.to]=1; 66 q.push(e.to); 67 } 68 } 69 } 70 } 71 if(oo==d[t]){ 72 return 0; 73 } 74 flow+=a[t]; 75 cost+=a[t]*d[t]; 76 for(rint i=t;i!=s;i=es[p[i]].from){ 77 es[p[i]].flow+=a[t]; 78 es[p[i]^1].flow-=a[t]; 79 } 80 return 1; 81 } 82 pil MaxfMinc(){ 83 int flow=0; 84 ll cost=0LL; 85 while(SPFA(flow,cost)); 86 return mp(flow,cost); 87 } 88 }D; 89 int n,m,s=0,t=MAXN-1; 90 int a[MAXN]; 91 void init(){ 92 D.init(t,s,t); 93 n=read(),m=read(); 94 for(rint i=1;i<=n;i++){ 95 a[i]=read(); 96 } 97 int x,y,z; 98 for(rint i=1;i<=m;i++){ 99 x=read(),y=read(),z=read();100 D.add(x,y+1,INF,1LL*z);101 }102 for(rint i=1;i<=n+1;i++){103 x=a[i]-a[i-1];104 if(x>0)D.add(s,i,x,0LL);105 else D.add(i,t,-x,0LL);106 if(i>1)D.add(i,i-1,INF,0LL);107 }108 }109 int main()110 {111 init();112 printf("%lld\n",D.MaxfMinc().second);113 return 0;114 }

转化为最小费用最大流

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #define rint register int 8 #define ll long long 9 #define MAXN 1000+10 10 #define pb push_back 11 #define INF 0x7f7f7f7f 12 #define oo 0x7f7f7f7f7f7f7f7f 13 #define pil pair
           
             14 #define mp make_pair 15 using namespace std; 16 int read(){ 17 int x=0,f=1;char ch=getchar(); 18 while(ch<'0'||ch>'9'){ if('-'==ch)f=-1;ch=getchar();} 19 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 struct E{ 23 int from,to,cap,flow; 24 ll cost; 25 E(int x=0,int y=0,int c=0,int f=0,ll w=0LL){ 26 from=x,to=y,cap=c,flow=f,cost=w; 27 } 28 }; 29 struct Dinic{ 30 int n,m,s,t; 31 vector
            
              es; 32 vector
             
               G[MAXN]; 33 void init(int n,int s,int t){ 34 this->n=n; 35 this->s=s,this->t=t; 36 es.clear(); 37 for(int i=0;i<=n;i++)G[i].clear(); 38 } 39 void add(int x,int y,int cap,ll cost){ 40 es.pb(E(x,y,cap,0,cost)); 41 es.pb(E(y,x,0,0,-cost)); 42 m=es.size(); 43 G[x].pb(m-2),G[y].pb(m-1); 44 } 45 int p[MAXN],a[MAXN]; 46 ll d[MAXN]; 47 int b[MAXN]; 48 bool SPFA(int &flow,ll &cost){ 49 p[s]=0,a[s]=INF; 50 memset(d,0x7f,sizeof(d)); 51 d[s]=0; 52 memset(b,0,sizeof(b)); 53 b[s]=1; 54 queue
              
                q; 55 q.push(s); 56 while(!q.empty()){ 57 int x=q.front();q.pop();b[x]=0; 58 for(rint i=0;i
               
                e.flow&&d[e.to]>d[x]+e.cost){ 61 p[e.to]=G[x][i]; 62 a[e.to]=min(a[x],e.cap-e.flow); 63 d[e.to]=d[x]+e.cost; 64 if(!b[e.to]){ 65 b[e.to]=1; 66 q.push(e.to); 67 } 68 } 69 } 70 } 71 if(oo==d[t]){ 72 return 0; 73 } 74 flow+=a[t]; 75 cost+=a[t]*d[t]; 76 for(rint i=t;i!=s;i=es[p[i]].from){ 77 es[p[i]].flow+=a[t]; 78 es[p[i]^1].flow-=a[t]; 79 } 80 return 1; 81 } 82 pil MaxfMinc(){ 83 int flow=0; 84 ll cost=0LL; 85 while(SPFA(flow,cost)); 86 return mp(flow,cost); 87 } 88 }D; 89 int n,m,s=0,t=MAXN-1; 90 int main() 91 { 92 D.init(t,s,t); 93 int k; 94 n=read(),m=read(); 95 for(rint i=1;i<=n;i++){ 96 k=read(); 97 D.add(i,i+1,INF-k,0LL); 98 } 99 D.add(s,1,INF,0LL);100 D.add(n+1,t,INF,0LL);101 int x,y;102 for(rint i=1;i<=m;i++){103 x=read(),y=read(),k=read();104 D.add(x,y+1,INF,1LL*k);105 }106 printf("%lld\n",D.MaxfMinc().second);107 return 0;108 }