目录
显示
题目链接
https://www.luogu.org/problem/P4015
题解
建模的方式并不是太难想:
- 从源点向所有仓库连一条流量为 \(a_i\),费用为 \(0\) 的边,代表该仓库供应量为 \(a_i\)。
- 从所有商店向汇点连一条流量为 \(b_i\),费用为 \(0\) 的边,代表该商店需求量为 \(b_i\)。
- 对于仓库 \(i\) 和商店 \(j\),在两者间连一条流量为 \(+\infty\),费用为 \(c_{i,j}\) 的边,代表运输的费用。
跑一次最小费用最大流和最大费用最大流即可。
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define INF 0x3f3f3f3f using namespace std; struct edge { int v,w,c,next; }e[40005]; struct node { int v,e; }p[205]; int head[205],dist[205],vis[205],cnt=1,s,t; void addedge(int u,int v,int w,int c) { e[++cnt].v=v; e[cnt].w=w; e[cnt].c=c; e[cnt].next=head[u]; head[u]=cnt; } bool spfa(int op) { queue<int> q; memset(dist,INF,sizeof(dist)); dist[s]=0,vis[s]=1; q.push(s); while(!q.empty()) { int cur=q.front(); q.pop(); vis[cur]=0; for(int i=head[cur];i;i=e[i].next) if(e[i].w&&dist[cur]+(e[i].c)*op<dist[e[i].v]) { dist[e[i].v]=dist[cur]+e[i].c*op; p[e[i].v].v=cur; p[e[i].v].e=i; if(!vis[e[i].v]) { vis[e[i].v]=1; q.push(e[i].v); } } } return dist[t]!=INF; } int mfmc(int op) { int ans=0; while(spfa(op)) { int minw=INF; for(int i=t;i!=s;i=p[i].v) minw=min(minw,e[p[i].e].w); for(int i=t;i!=s;i=p[i].v) { e[p[i].e].w-=minw; e[p[i].e^1].w+=minw; } ans+=minw*dist[t]*op; } return ans; } int main() { int m,n; scanf("%d%d",&m,&n); s=m+n+1,t=m+n+2; for(int i=1;i<=m;i++) { int x; scanf("%d",&x); addedge(s,i,x,0); addedge(i,s,0,0); } for(int i=1;i<=n;i++) { int x; scanf("%d",&x); addedge(i+m,t,x,0); addedge(t,i+m,0,0); } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { int x; scanf("%d",&x); addedge(i,j+m,INF,x); addedge(j+m,i,0,-x); } printf("%d\n",mfmc(1)); for(int i=2;i<=cnt;i+=2) e[i].w+=e[i^1].w,e[i^1].w=0; printf("%d\n",mfmc(-1)); return 0; }