首先对于一种商品

如果这种货不足需求就直接输出-1

剩下的就是KM算法

分k次分别计算每种商品的最小权值匹配

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,k,shop[][],sup[][],cost[][][],edges[][],cntA,cntB;
int belongA[],belongB[],A[],B[],visA[],visB[],mat[],d;
int dfs(int i)
{
visA[i]=;
for (int j=;j<=cntB;j++)
if (!visB[j]&&edges[i][j])
{
int t=edges[i][j]-A[i]-B[j];
if (!t)
{
visB[j]=;
if (!mat[j]||dfs(mat[j]))
{
mat[j]=i;
return ;
}
}
else d=min(d,t);
}
return ;
}
int match()
{
memset(A,0x3f,sizeof(A));
memset(B,,sizeof(B));
for (int i=;i<=cntA;i++)
for (int j=;j<=cntB;j++)A[i]=min(A[i],edges[i][j]);
memset(mat,,sizeof(mat));
for (int i=;i<=cntA;i++)
{
while ()
{
memset(visA,,sizeof(visA));
memset(visB,,sizeof(visB));
d=1e9;
if (dfs(i))break;
for (int j=;j<=cntA;j++)
if (visA[j]) A[j]+=d;
for (int j=;j<=cntB;j++)
if (visB[j]) B[j]-=d;
}
}
int ans=;
for (int i=;i<=cntB;i++)ans+=edges[mat[i]][i];
return ans;
}
int main()
{
while (~scanf("%d%d%d",&n,&m,&k),n+m+k)
{
for (int i=;i<=n;i++)
for (int j=;j<=k;j++)scanf("%d",&shop[i][j]);
for (int i=;i<=m;i++)
for (int j=;j<=k;j++)scanf("%d",&sup[i][j]);
for (int t=;t<=k;t++)
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)scanf("%d",&cost[t][i][j]);
int flag=;
for (int i=;i<=k;i++)
{
int need=,have=;
for (int j=;j<=n;j++)need+=shop[j][i];
for (int j=;j<=m;j++)have+=sup[j][i];
if (need>have)
{
flag=;
puts("-1");
break;
}
}
if (!flag)continue;
int ans=;
for (int t=;t<=k;t++)
{
cntA=cntB=;
for (int i=;i<=n;i++)
for (int j=;j<=shop[i][t];j++)belongA[++cntA]=i;
for (int i=;i<=m;i++)
for (int j=;j<=sup[i][t];j++)belongB[++cntB]=i;
for (int i=;i<=cntA;i++)
for (int j=;j<=cntB;j++)
edges[i][j]=cost[t][belongA[i]][belongB[j]];
ans+=match();
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. windows系统快捷操作の基础篇
  2. 软件工程(C编码实践篇)课程总结
  3. Android 中的selector
  4. Nginx 笔记与总结(8)Location:归纳总结
  5. IOS自动布局
  6. android拦截短信并屏蔽系统的Notification
  7. C#关于编码、解码相关问题
  8. 网络流(最大流) CQOI 2015 BZOJ 3931 网络吞吐量
  9. 实验用rootkit
  10. MySQL优化四(优化表结构)
  11. json api
  12. CSS3字体发光效果
  13. CAS 之 Apereo CAS 简介(一)
  14. WebApi PUT、DELETE请求时出现405 - 不允许用于访问此页的 HTTP 谓词。
  15. 软件工程第二次作业-VSTS单元测试
  16. CSS奇淫技巧
  17. python scrapy 报错 DEBUG: Ignoring response 403
  18. vs 2017 集成python
  19. 主元素问题 Majority Element
  20. sqlserver 日志查看

热门文章

  1. Loadrunner自带协议分析工具:Protocol Advisor
  2. hdfs启动后进入safe mode,Problem connecting to server
  3. 高通camera结构(摄像头基础介绍)
  4. 【Head First Servlets and JSP】笔记 27: web 应用安全
  5. Visual Studio 2010生成解决方案时,导致C盘空间越来越小
  6. 配置hadoop集群的lzo压缩
  7. [翻译]小提示:使用figure和figcaption元素的正确方式
  8. 100个gdb调试技巧
  9. mysql中group by存在局限性探讨(待续)
  10. 【分类】AlexNet论文总结