题目
https://www.luogu.com.cn/problem/P4015
思路
货物供需平衡,要求总运输费用最小,那就很显然是最小费用最大流了。
考虑如何建图。我们将每个仓库看成一个结点,每个商店看成一个结点。建一个超级源 \(S\) 和超级汇 \(T\) ,从S向每个仓库各连一条容量为 \(a_{i}\) ,费用为 \(0\) 的边,表示每个仓库最多运出这么多(通过控制入量来限制出量)。从每个商店向 \(T\) 连一条容量为 \(b_{i}\) ,费用为 \(0\) 的边,表示每个商店需要接收到这么多货物(这样在满流的情况下必定保证商店结点的入量\(=b{i}\))。
最后在仓库和商店间连边。仓库 \(i\) 到商店 \(j\) 的边,容量为 \(inf\) ,费用为 \(c_{ij}\) ,由于之前的边已经能起到限制流量的功能,所以容量可以设置为 \(\geq a_{i}\) 的任意整数。
注意别忘了建反向边。
这种题其实也是相当套路,存在明显的对应关系(可看成左右两排结点),而且有比较明显可看做流量的东西(货物,题面中"供需平衡"这个关键词就是很明显的提示)。接下来只要按照题意建出符合限制关系的图,丢板子跑费用流就好了。
代码
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int a[110],b[110];
int S,T;
int fst[300],nxt[100000],cnt=0;
int dis[300],visit[300],pre[300];
struct edge{
int from,to,cap,flow,val;
} e[100000];
void add(int x,int y,int z,int f,int w){
e[++cnt].from=x;
e[cnt].to=y;
e[cnt].cap=z;
e[cnt].flow=f;
e[cnt].val=w;
nxt[cnt]=fst[x];
fst[x]=cnt;
}
int spfa(){
int i;
memset(dis,inf,sizeof(dis));
memset(visit,0,sizeof(visit));
memset(pre,0,sizeof(pre));
queue<int> q;
q.push(S);
visit[S]=1;
dis[S]=0;
while(!q.empty()){
int p=q.front();
q.pop();visit[p]=0;
for(i=fst[p];i;i=nxt[i]){
if(e[i].flow<e[i].cap&&dis[p]+e[i].val<dis[e[i].to]){
dis[e[i].to]=dis[p]+e[i].val;
pre[e[i].to]=i;
if(!visit[e[i].to]){
q.push(e[i].to);
visit[e[i].to]=1;
}
}
}
}
return dis[T];
}
int inv(int x){
return ((x-1)^1)+1;
}
int max_flow(int flag){
int sum=0,d,f;
while((d=spfa())<inf){
f=inf;
for(int p=T;p!=S;p=e[pre[p]].from){
f=min(f,e[pre[p]].cap-e[pre[p]].flow);
}
sum+=d*f;
for(int p=T;p!=S;p=e[pre[p]].from){
e[pre[p]].flow+=f;
e[inv(pre[p])].flow-=f;
}
}
return sum*flag;
}
int main(){
int i,j,n,m,x,ans1,ans2;
scanf("%d%d",&n,&m);
S=n+m+1;T=S+1;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
add(S,i,a[i],0,0);add(i,S,0,0,0);
}
for(i=1;i<=m;i++){
scanf("%d",&b[i]);
add(n+i,T,b[i],0,0);add(T,n+i,0,0,0);
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&x);
add(i,n+j,a[i],0,x);
add(n+j,i,0,0,-x);
}
}
ans1=max_flow(1);
for(i=1;i<=cnt;i++){
e[i].val*=-1;
e[i].flow=0;
}
ans2=max_flow(-1);
printf("%d\n%d",ans1,ans2);
// system("pause");
return 0;
}
PS:数据挺弱的,裸的spfa能跑过