[洛谷 4015]运输问题

题目链接

https://www.luogu.org/problem/P4015

题解

建模的方式并不是太难想：

1. 从源点向所有仓库连一条流量为 \(a_i\)，费用为 \(0\) 的边，代表该仓库供应量为 \(a_i\)。
2. 从所有商店向汇点连一条流量为 \(b_i\)，费用为 \(0\) 的边，代表该商店需求量为 \(b_i\)。
3. 对于仓库 \(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;
}