题目描述：
输入格式：
输出格式：
两行分别输出最小运输费用和最大运输费用。
输入输出样例：
输入 #1
2 3
220 280
170 120 210
77 39 105
150 186 122
输出 #1
48500
69140
题解：
最小费用最大流(MCMF)问题
根据样例数据分析：
橙色为第一个仓库晕倒各零售商店的单位费用
绿色为第二个
一边是仓库，一边是商店，典型的二分图，还是完全二分图
我们可以在仓库的左边设置一个源点S，右边设置一个终点T。S指向每一个仓库，容量为ai，费用为0，而每一个商店指向T，容量为bi，费用为0
从仓库到商店的边容量是min（仓库货物量ai，商店容量bi），费用为读入的值
为了方便处理，我们可以将S点记为编号1，仓库为编号1 ~ m，商店为m+1 ~ n+m，T点为201
然后直接跑最小费用最大流就可以了
找到最大后，将费用取反再跑一遍即可找到最小
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#define I_copy_this_answer return 0;
using namespace std;
int n,m,head[1100];
int cnt=1;
int mincost,maxwater;
int flow[1100];
int b[1100],cost[310][310];
int pre[1100],last[1100],dis[1100],vis[1100],a[1100];
int s=0;
//last记录边，pre记录点
struct node{
int next,to,dis,flow;
}edge[100860];
void addedge(int next,int to,int dis,int flow)
{
edge[++cnt].to=to;
edge[cnt].dis=dis;
edge[cnt].flow=flow;
edge[cnt].next=head[next];
head[next]=cnt;
}
int spfa()
{
memset(flow,0x3f,sizeof(flow));
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
queue <int> q;
q.push(s);
dis[s]=0;
vis[s]=1;
pre[201]=-1; //初始化汇点的前点
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
int w=edge[i].dis;
int l=edge[i].flow;
if(dis[u]+w<dis[v]&&l>0) //没有流量的话这条路就增广不了，最短距离是建立在增广路存在的基础上的
{
dis[v]=dis[u]+w;
last[v]=i; //last指的是这个点(v)与上个点(u)相连的边的编号
pre[v]=u; //pre指的是这条路径上这个点(v)的上一个点
flow[v]=min(flow[u],l); //把当前边流量与上个点的流量对比，解决出现仓库货物比需要的少的情况
if(!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
return pre[201]!=-1; //如果不是这个值就说明这个点被刷新，增广成功
}
void mcmf()
{
while(spfa())
{
mincost+=dis[201]*flow[201]; //从源点出发到汇点的单位费用再乘以单位，由于每次只增广一条路，而且仓库和商店是直接连接的，可以这样写
int t=201;
while(t!=0)
{
edge[last[t]].flow-=flow[201]; //回溯，修改每条边的流量，因为该算法中途找到的增广路不是最后的增广路，所以这个要等到最后来改变
edge[last[t]^1].flow+=flow[201];
t=pre[t];
}
}
}
void build_edge(int t)//t用来控制边权的正负，为了方便求最小和最大
{
for(int i=1;i<=m;i++)
{
addedge(0,i,0,a[i]);
addedge(i,0,0,0);//与源点S相连
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
addedge(i,j+m,cost[i][j]*t,b[j]);
addedge(j+m,i,-cost[i][j]*t,0);//仓库与商店相连
}
for(int i=1;i<=n;i++)
{
addedge(i+m,201,0,b[i]);//与汇点T相连
addedge(201,i+m,0,0);
}
}
int main()
{
int i,j;
scanf("%d %d",&m,&n);
for(i=1;i<=m;i++)
{
int t1;
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]); //仓库与商店的边权
build_edge(1); //建立边权为正的边，跑最小费用最大流
mcmf();//最小费用最大流(Min Cost Max Flow ）的缩写
printf("%d",mincost);
maxwater=0;
mincost=0;
cnt=1;
memset(head,0,sizeof(head));
build_edge(-1);//建立边权为符的边
mcmf();
printf("\n%d",-mincost);
}
京公网安备 11010502036488号