题意:有n个商店,每个商店有k种货物,每个货物需要a[n][k]个,有m个仓库,每个仓库也有k种货物,每个货物有b[m][k]个,然后k个矩阵,每个矩阵都是n*m的,第i行第j列表示从仓库j到商店i每单位k货物的花费,问你最小的花费满足商店,不行输出-1;
解题思路:刚开始以为是拆点费用流,然后会超时。。。后面看别人是直接对每一种货物都建图跑费用流,这样就行了,建一个汇点和源点,源点连向仓库,仓库连向商店,商店连向汇点;
代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=100500;
const int inf=0x3f3f3f3f;
struct Edge
{
int next;
int to;
int w;
int cost;
}edge[maxn];
int head[maxn],dist[maxn],pre[maxn],path[maxn];
int cnt,x,y,w,n,m,k;
int Start,End;
int a[205][205],b[205][205],c[205][205][205];
int need[205],sup[205];
void add(int u,int v,int w,int cost)
{
// cout<<u<<" "<<v<<" "<<w<<" "<<cost<<endl;
edge[cnt].next=head[u];edge[cnt].to=v;
edge[cnt].w=w;edge[cnt].cost=cost;head[u]=cnt++;
//建回边
edge[cnt].next=head[v];edge[cnt].to=u;
edge[cnt].w=0;edge[cnt].cost=-cost;head[v]=cnt++;
}
bool spfa(int s,int t)
{
memset(pre,-1,sizeof(pre));
memset(dist,inf,sizeof(dist));
dist[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())//不能有环,建图的时候也要注意
{
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].w>0&&dist[u]+edge[i].cost<dist[v])//这条路径存在且能被优化
{
dist[v]=dist[u]+edge[i].cost;
pre[v]=u;path[v]=i;q.push(v);
}
}
}
if(pre[t]==-1)
return false;
return true;
}
int mincost(int s,int t)
{
int cost=0;int flow=0;
while(spfa(s,t))
{
int tempflow=inf;
for(int u=t;u!=s;u=pre[u])//找最小的流量
{
if(edge[path[u]].w<tempflow)
tempflow=edge[path[u]].w;
}
flow+=tempflow;//每增广一次能得到的流量;
cost+=dist[t]*tempflow;//花费
//cost+=dist[t];
for(int u=t;u!=s;u=pre[u])
{
edge[path[u]].w-=tempflow;
edge[path[u]^1].w+=tempflow;
}
//cout<<cost<<endl;
}
return cost;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
memset(need,0,sizeof(need));
memset(sup,0,sizeof(sup));
Start=0;End=n+m+1;
int flag=0;
if(n==0&&m==0&&k==0)
break;
for(int i=1;i<=n;i++)//商店需要的
for(int j=1;j<=k;j++)
{
scanf("%d",&a[i][j]);
need[j]+=a[i][j];
}
for(int i=1;i<=m;i++)//仓库提供的
for(int j=1;j<=k;j++)
{
scanf("%d",&b[i][j]);
sup[j]+=b[i][j];
}
for(int i=1;i<=k;i++)//最小花费
for(int j=1;j<=n;j++)
for(int l=1;l<=m;l++)
scanf("%d",&c[i][j][l]);
for(int i=1;i<=k;i++)
{
if(sup[i]<need[i])
{
flag=1;
}
}
if(flag)
{
printf("-1\n");continue;
}
int ans=0;
for(int i=1;i<=k;i++)
{
memset(head,-1,sizeof(head));cnt=0;
for(int j=1;j<=m;j++)
add(Start,j,b[j][i],0);
for(int j=1;j<=n;j++)
add(j+m,End,a[j][i],0); for(int j=1;j<=n;j++)
for(int l=1;l<=m;l++)
{
add(l,j+m,inf,c[i][j][l]);
}
ans+=mincost(Start,End);
}
printf("%d\n",ans);
}
}