bzoj4950 [Wf2017]Mission Improbable

bzoj4950 [Wf2017]Mission Improbable

​​ Description

那是春日里一个天气晴朗的好日子,你准备去见见你的老朋友Patrick,也是你之前的犯罪同伙。Patrick在编程竞赛 上豪赌输掉了一大笔钱,所以他需要再干一票。为此他需要你的帮助,虽然你已经金盆洗手了。你刚开始很不情愿, 因为你一点也不想再回到那条老路上了,但是你觉得听一下他的计划也无伤大雅。在附近的一个仓库里有一批货物, 包含一些贵重的消费性部件,Patrick企图从中尽可能多地偷些东西出来。这意味着要找一条进去的路,弄晕安保人 员,穿过各种各样的激光射线,你懂的,都是常见的抢劫技术。然而,仓库的核心装备了一套Patrick搞不定的安保系 统。这也是他需要你帮助他的地方。这批货物被放置在一些巨大的立方体箱里,每个箱子的尺寸都是相同的。这些 箱子堆放成许多整齐的堆,每个箱子可以表示成一个三维的网格。安保系统每个小时会用三台相机对这堆货物进行 一次拍照,相机分别为:前置相机(front camera),侧置相机(side camera)和顶置相机(top camera)。前置相机的照 片显示了每一行最高的那堆箱子的高度,侧置相机显示了每一列最高的那堆箱子的高度,顶置相机显示了每个位置是 否存在一堆箱子。如果安保系统发现任何一张照片出现了变化,它会立即拉响警报。一旦 Patrick 进去了,他会确 定每堆箱子的高度并且发给你。图1显示了一种网格可能的放置,以及每台相机会得到的视图。

图 1. 网格的高度值与对应的相机视图。

图 2. 洗劫后网格可能的高度值。

Patrick想尽可能多偷走一些箱子。由于他不能弄坏安保系统,他准备重新安排剩余每堆箱子的放置,使得下一次相 机取像时会得到相同的照片,从而骗过安保系统。在上面的例子中,他可以偷走九个箱子。图2显示了一种可能的剩 余箱子的安置方案能使得安保系统认为与原安置情况相同。Patrick想请你帮他确定在保证能骗过安保系统的情况 下他最多能偷走多少个箱子。你会帮他干完这最后一票么? Input

第一行包含两个整数r(1≤r≤100)和c(1≤n≤100),分别表示网格的行数与列数。 接下来r行,每行包含c个整数,表示对应行上每堆立方体箱的高度(箱子的数量)。 所有的高度在0到10^9之间 (含边界) 。 Output

输出在不被发现的情况下最多能偷走多少箱子。 Sample Input

样例1 5 5 1 4 0 5 2 2 1 2 0 1 0 2 3 4 4 0 3 0 3 1 1 2 2 1 1 样例2 2 3 50 20 3 20 10 3 Sample Output

样例1 9 样例2 30 HINT

Source

鸣谢Tangjz提供翻译

程序很短但是写程序之前确实思考了很久（其实这个leoly 一个月前讲的题 orz 因为二分图匹配一直不会，留到今天

我们观察这个可以发现（小学奥数性质）那就是我们每一个非0的地方都覆盖1就可以了 其他地方，每行每列都覆盖最大值

我们因为尽可能拿走，那尤其是行列相同的时候 我们用一个这么高的就可以解决问题，就给答案加上这个

还有一个问题一开始没想清，要是这两个最大值正好相同但是那行那列对应正好原来是0怎么办 那干脆建图的时候就不要建就好啊

每行每列减去最大值的时候也要尤其小心值为0的情况

#include#include#include#define N 110using namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}long long ans;struct node{ int y,next;}data[N*N];int r,c,h[N],maxl[N],maxc[N],map[N][N],num,girl[N<<1];bool used[N<<1];inline bool judge(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if(used[y]) continue;used[y]=true; if (!girl[y]||judge(girl[y])){ girl[y]=x;return true; } } return false;}int main(){ freopen("bzoj4950.in","r",stdin); r=read();c=read(); for (int i=1;i<=r;++i) for (int j=1;j<=c;++j){ map[i][j]=read();maxl[i]=max(maxl[i],map[i][j]);maxc[j]=max(maxc[j],map[i][j]); if (map[i][j]) ans+=map[i][j]-1; } for (int i=1;i<=r;++i) for (int j=1;j<=c;++j) if(maxl[i]==maxc[j]&&map[i][j]) data[++num].y=r+j,data[num].next=h[i],h[i]=num; for (int i=1;i<=r;++i) if (maxl[i]) ans-=maxl[i]-1; for (int i=1;i<=c;++i) if (maxc[i]) ans-=maxc[i]-1; for (int i=1;i<=r;++i) { memset(used,0,sizeof(used));if (judge(i)) ans+=maxl[i]-1; } printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。