s 向仓库 i 连 ins(s,i,a[i],0), 商店向 t 连 ins(i+m,t,b[i],0), 商店和仓库之间连 ins(i,j+m,inf,c[i][j]) 建两次图分别跑最小费用最大流和最大费用最大流即可
- #include<iostream>
- #include<cstdio>
- #include<queue>
- #include<cstring>
- using namespace std;
- const int N=1000005,inf=1e9;
- int n,m,h[N],cnt=1,dis[N],fr[N],ans,s,t,a[105],b[105],c[105][105];
- bool v[N];
- struct qwe
- {
- int ne,no,to,va,c;
- }e[N<<2];
- int read()
- {
- int r=0,f=1;
- char p=getchar();
- while(p>9||p<0)
- {
- if(p==-)
- f=-1;
- p=getchar();
- }
- while(p>=0&&p<=9)
- {
- r=r*10+p-48;
- p=getchar();
- }
- return r*f;
- }
- void add(int u,int v,int w,int c)
- {
- cnt++;
- e[cnt].ne=h[u];
- e[cnt].no=u;
- e[cnt].to=v;
- e[cnt].va=w;
- e[cnt].c=c;
- h[u]=cnt;
- }
- void ins(int u,int v,int w,int c)
- {//cout<<u<<""<<v<<" "<<w<<endl;
- add(u,v,w,c);
- add(v,u,0,-c);
- }
- bool spfa1()
- {
- queue<int>q;
- for(int i=s;i<=t;i++)
- dis[i]=inf;
- dis[s]=0;
- v[s]=1;
- q.push(s);
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- v[u]=0;
- for(int i=h[u];i;i=e[i].ne)
- if(e[i].va>0&&dis[e[i].to]>dis[u]+e[i].c)
- {
- dis[e[i].to]=dis[u]+e[i].c;
- fr[e[i].to]=i;
- if(!v[e[i].to])
- {
- v[e[i].to]=1;
- q.push(e[i].to);
- }
- }
- }
- return dis[t]!=inf;
- }
- bool spfa2()
- {
- queue<int>q;
- for(int i=s;i<=t;i++)
- dis[i]=-inf;
- dis[s]=0;
- v[s]=1;
- q.push(s);
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- v[u]=0;
- for(int i=h[u];i;i=e[i].ne)
- if(e[i].va>0&&dis[e[i].to]<dis[u]+e[i].c)
- {
- dis[e[i].to]=dis[u]+e[i].c;
- fr[e[i].to]=i;
- if(!v[e[i].to])
- {
- v[e[i].to]=1;
- q.push(e[i].to);
- }
- }
- }
- return dis[t]!=-inf;
- }
- void mcf()
- {//cout<<"OK"<<endl;
- int x=inf;
- for(int i=fr[t];i;i=fr[e[i].no])
- x=min(x,e[i].va);
- for(int i=fr[t];i;i=fr[e[i].no])
- {
- e[i].va-=x;
- e[i^1].va+=x;
- ans+=x*e[i].c;
- }
- }
- int main()
- {
- m=read(),n=read();
- s=0,t=n+m+1;
- for(int i=1;i<=m;i++)
- a[i]=read();
- for(int i=1;i<=n;i++)
- b[i]=read();
- for(int i=1;i<=m;i++)
- for(int j=1;j<=n;j++)
- c[i][j]=read();
- for(int i=1;i<=m;i++)
- ins(s,i,a[i],0);
- for(int i=1;i<=n;i++)
- ins(i+m,t,b[i],0);
- for(int i=1;i<=m;i++)
- for(int j=1;j<=n;j++)
- ins(i,j+m,inf,c[i][j]);
- while(spfa1())
- mcf();
- printf("%d\n",ans);
- memset(h,0,sizeof(h));
- cnt=1,ans=0;
- for(int i=1;i<=m;i++)
- ins(s,i,a[i],0);
- for(int i=1;i<=n;i++)
- ins(i+m,t,b[i],0);
- for(int i=1;i<=m;i++)
- for(int j=1;j<=n;j++)
- ins(i,j+m,inf,c[i][j]);
- while(spfa2())
- mcf();
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2495155.html