首页 > 代码库 > [haoi2010]订货 最小费用流
[haoi2010]订货 最小费用流
这道题oj上的标签是动态规划，但我想不出来动态规划怎么搞，空间不爆，时间也要爆的；
好的，不扯淡，此题正常做法是最小费用流；
这道题我写了两遍，为什么呢？原因是第一次写的时候，不会写费用流，又恰好没带书，所以搁置了；
第二次又写到这道题了，有点生气，一鼓作气学了费用流，紧跟着敲了这道题；
也算一道费用流模板吧；
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 using namespace std; 7 const int maxn=500; 8 const int inf=10000000; 9 const int S=0,T=50+1;10 struct node{11 int x,y,next,flow,v,re;12 }e[maxn];13 int linkk[maxn],len=0,n,m,s,u[maxn],c[maxn];14 void insert(int x,int y,int flow,int v){15 e[++len].x=x;16 e[len].y=y;17 e[len].v=v;18 e[len].flow=flow;19 e[len].next=linkk[x];20 e[len].re=len+1;21 linkk[x]=len;22 e[++len].x=y;23 e[len].y=x;24 e[len].flow=0;25 e[len].v=v;26 e[len].next=linkk[y];27 e[len].re=len-1;28 linkk[y]=len;29 }30 void init(){31 scanf("%d%d%d",&n,&m,&s);32 for(int i=1;i<=n;i++)scanf("%d",&u[i]);33 for(int i=1;i<=n;i++)scanf("%d",&c[i]);34 for(int i=1;i<=n;i++){35 insert(S,i,inf,c[i]);insert(i,T,u[i],0);36 }37 for(int i=1;i<n;i++)insert(i,i+1,s,m);38 }39 int vis[maxn],d[maxn],q[maxn*maxn],head=0,tail=0,pre[maxn],ans=0,cap[maxn],t[maxn];40 bool SPFA(){41 for(int i=S;i<=T;i++)d[i]=inf<<2;42 memset(vis,0,sizeof(vis));43 head=0,tail=0;44 q[++tail]=S;d[S]=0;45 while(++head<=tail){46 int x=q[head];47 vis[x]=0;48 for(int i=linkk[x];i;i=e[i].next){49 if(e[i].flow&&d[e[i].y]>d[x]+e[i].v){50 d[e[i].y]=d[x]+e[i].v;51 cap[e[i].y]=e[i].flow;52 t[e[i].y]=i;53 pre[e[i].y]=x;54 if(!vis[e[i].y]){55 vis[e[i].y]=1;56 q[++tail]=e[i].y;57 }58 }59 }60 }61 if(d[T]==inf<<2)return 0;62 int flow=inf;63 for(int i=T;i!=S;i=pre[i])flow=min(flow,cap[i]);64 for(int i=T;i!=S;i=pre[i]){65 e[t[i]].flow-=flow;66 e[e[t[i]].re].flow+=flow;67 ans+=e[t[i]].v*flow;68 }69 return 1;70 }71 void work(){72 ans=0;73 while(SPFA());74 cout<<ans<<endl;75 }76 int main(){77 init();78 work();79 }
[haoi2010]订货 最小费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。