跟着靖靖做题%%%%%

这题一看就觉得和之前的某场模拟赛的一道题很像,找假如某行某列的最大值一样的就可以只堆一个,跑匈牙利就行

一开始以为箱子不能移动-_-!

然后有个坑,大家都知道当这个位置有箱子就偷剩一个,但是假如当前行当前列没有箱子,就算他们最大值一样也不能建边

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath> #define pd(a,b,c,d) a==b?c:d
using namespace std;
typedef long long LL; int n,m;LL c[][];
LL hmx[],lmx[];
void get_max()
{
for(int i=;i<=n;i++)
{
hmx[i]=;
for(int j=;j<=m;j++)
hmx[i]=max(hmx[i],c[i][j]);
}
for(int j=;j<=m;j++)
{
lmx[j]=;
for(int i=;i<=n;i++)
lmx[j]=max(lmx[j],c[i][j]);
}
} //----------init------------- struct node
{
int x,y,next;
}a[];int len,last[];
void ins(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
void composition()//二分图匹配旨在解决某点同时作为hmx和lmx情况
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(hmx[i]==lmx[j]&&c[i][j]!=)ins(i,j);
}
int tim,v[];
int match[];
bool findmuniu(int x)
{
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(v[y]!=tim)
{
v[y]=tim;
if(match[y]==||findmuniu(match[y])==true)
{
match[y]=x;
return true;
}
}
}
return false;
} //----------match------------- int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%lld",&c[i][j]);
get_max();
LL ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
ans+=pd(c[i][j],,,c[i][j]-);
for(int i=;i<=n;i++)ans-=pd(hmx[i],,,hmx[i]-);
for(int j=;j<=m;j++)ans-=pd(lmx[j],,,lmx[j]-); composition();
memset(match,,sizeof(match));
memset(v,,sizeof(v));tim=;
for(int i=;i<=n;i++)
{
tim++;
if(findmuniu(i)==true)ans+=pd(hmx[i],,,hmx[i]-);
}
printf("%lld\n",ans);
return ;
}

最新文章

  1. No.004:Median of Two Sorted Arrays
  2. css3 三角形
  3. shh简化
  4. centOS安装Mysql指南
  5. serv-u设置被动模式注意的问题
  6. 百度的domain命令到底有用吗?
  7. gson小练习之嵌套复杂数据解析
  8. proxy.ini文件调用
  9. idea_intellij
  10. 基于TF-IDF的新闻标签提取
  11. oracle常用函数及关键字笔记
  12. dojo省份地市级联之地市封装类(二)
  13. 【MyBatis源码分析】环境准备
  14. pache tomcat慢速HTTP拒绝服务攻击安全问题解决办法
  15. Trident Topology开发Demo
  16. autorelease&#39; is unavailable
  17. JavaScript 条件判断算法综合实战
  18. LeetCode--345--反转字符串中的元音字母
  19. golang中的接口实现(二)
  20. Qt 随机数

热门文章

  1. Android FileProvider相关 Failed to find configured root that contains
  2. Less——less基本使用
  3. html5——渐变
  4. XML在线转化为JSON
  5. 洛谷——P2814 家谱
  6. CF51F Caterpillar (边双+树形DP)
  7. springcloud(七): 使用Feign调用Eureka Server客户端服务
  8. Java 下实现Cache
  9. http长链接问题
  10. UVALIVE 6958 Indoorienteering