新费用流建图技巧get
显然可以把每个厨师拆成\(\sum p\)个跑费用流
但是(你们又不高兴)这样跑会很慢,那怎么办?
开始只设\(m\)个厨师表示该厨师最后一次做的菜,增广完将被增广的厨师新建一个点作为他倒数第二次做的菜,代价翻倍,以此类推
脑补一下是对的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
// <2879.cpp> - 01/02/17 14:14:08 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=2010; const int MAXM=2000010; const int N=41; const int M=110; const int INF=1e9; int bt=1,b[MAXN],next[MAXM],to[MAXM],val[MAXM],cost[MAXM]; inline void add(int x,int y,int z,int c){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;cost[bt]=c; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=0;cost[bt]=-c; } int T,p[N],t[N][M]; queue <int> q; int dis[MAXN],pre[MAXN]; bool in[MAXN]; bool fc(){ for(int i=1;i<=T;i++)dis[i]=INF,pre[i]=0; q.push(0); while(!q.empty()){ int x=q.front();q.pop();in[x]=0; for(int i=b[x];i;i=next[i]){ if(!val[i]||dis[x]+cost[i]>=dis[to[i]])continue; dis[to[i]]=dis[x]+cost[i]; pre[to[i]]=i; if(in[to[i]])continue; in[to[i]]=1; q.push(to[i]); } } return dis[T]!=INF; } int get(){ int f=INF; for(int i=pre[T];i;i=pre[to[i^1]])f=min(f,val[i]); for(int i=pre[T];i;i=pre[to[i^1]]){ val[i]-=f; val[i^1]+=f; } return dis[T]*f; } int tot,pos[M],cnt[M]; int main(){ int n=gi(),m=gi(),sum=0; for(int i=1;i<=n;i++)sum+=p[i]=gi(); T=n+m+sum+1; for(int i=1;i<=n;i++){ add(0,i,p[i],0); for(int j=1;j<=m;j++)add(i,n+j,1,t[i][j]=gi()); } for(int i=1;i<=m;i++)add(pos[i]=n+i,T,1,0),cnt[i]=1; int ans=0; for(int k=1;k<=sum;k++){ fc();ans+=get(); int p; for(p=1;val[b[pos[p]]];p++); cnt[p]++;pos[p]=n+m+k; for(int i=1;i<=n;i++)add(i,pos[p],1,t[i][p]*cnt[p]); add(pos[p],T,1,0); } printf("%d",ans); return 0; } |