poj21516
2024-10-19 06:28:10
首先对于一种商品
如果这种货不足需求就直接输出-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 ;
}
最新文章
- windows系统快捷操作の基础篇
- 软件工程(C编码实践篇)课程总结
- Android 中的selector
- Nginx 笔记与总结(8)Location:归纳总结
- IOS自动布局
- android拦截短信并屏蔽系统的Notification
- C#关于编码、解码相关问题
- 网络流(最大流) CQOI 2015 BZOJ 3931 网络吞吐量
- 实验用rootkit
- MySQL优化四(优化表结构)
- json api
- CSS3字体发光效果
- CAS 之 Apereo CAS 简介(一)
- WebApi PUT、DELETE请求时出现405 - 不允许用于访问此页的 HTTP 谓词。
- 软件工程第二次作业-VSTS单元测试
- CSS奇淫技巧
- python scrapy 报错 DEBUG: Ignoring response 403
- vs 2017 集成python
- 主元素问题 Majority Element
- sqlserver 日志查看
热门文章
- Loadrunner自带协议分析工具:Protocol Advisor
- hdfs启动后进入safe mode,Problem connecting to server
- 高通camera结构(摄像头基础介绍)
- 【Head First Servlets and JSP】笔记 27: web 应用安全
- Visual Studio 2010生成解决方案时,导致C盘空间越来越小
- 配置hadoop集群的lzo压缩
- [翻译]小提示:使用figure和figcaption元素的正确方式
- 100个gdb调试技巧
- mysql中group by存在局限性探讨(待续)
- 【分类】AlexNet论文总结