bzoj4950: [Wf2017]Mission Improbable
2024-08-31 02:32:54
跟着靖靖做题%%%%%
这题一看就觉得和之前的某场模拟赛的一道题很像,找假如某行某列的最大值一样的就可以只堆一个,跑匈牙利就行
一开始以为箱子不能移动-_-!
然后有个坑,大家都知道当这个位置有箱子就偷剩一个,但是假如当前行当前列没有箱子,就算他们最大值一样也不能建边
#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 ;
}
最新文章
- No.004:Median of Two Sorted Arrays
- css3 三角形
- shh简化
- centOS安装Mysql指南
- serv-u设置被动模式注意的问题
- 百度的domain命令到底有用吗?
- gson小练习之嵌套复杂数据解析
- proxy.ini文件调用
- idea_intellij
- 基于TF-IDF的新闻标签提取
- oracle常用函数及关键字笔记
- dojo省份地市级联之地市封装类(二)
- 【MyBatis源码分析】环境准备
- pache tomcat慢速HTTP拒绝服务攻击安全问题解决办法
- Trident Topology开发Demo
- autorelease&#39; is unavailable
- JavaScript 条件判断算法综合实战
- LeetCode--345--反转字符串中的元音字母
- golang中的接口实现(二)
- Qt 随机数