4950: [Wf2017]Mission Improbable
Time Limit: 1 Sec Memory Limit: 512 MB
Submit: 608 Solved: 222
[Submit][Status][Discuss]
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
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
9
样例2
30
这个题乍一看上去可能不是很容易想出来做法，不过动动脑子也就可以知道，俯视图就是要求当前有箱子的格子至少留一个，然后左视图和正视图就是要求每行每列的最大值不能变化。嗯，可以考虑一下贪心，就是只要不是最大的就通通拿走。事实证明这种贪心是非常可行的，但是也有缺陷，就是可能有那么一行一列的箱子的最大值是相同的，这个时候把最大值放在交点处很明显就要比放在其它的地方要好的多。那么如何限制呢？想到一个叫游戏的题，就是把每一行和每一列都当做点，然后用流量表示限制，嗯，貌似可以出解了。。。然后注意数组什么的要开大，数据很大要LL。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define inf 400000000000000ll
#define MAXN 205
#define MAXM 1000001
#define ll long long
using namespace std;
int cur[];
struct po
{
ll nxt,to,w;
}edge[MAXM];
int head[MAXN],dep[MAXN],num=-;
int l[MAXN],h[MAXN],a[][];
int n,m,s,t;
ll ans;
inline int read()
{
int x=,c=;
char ch=' ';
while((ch>''||ch<'')&&ch!='-')ch=getchar();
while(ch=='-')c*=-,ch=getchar();
while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();
return x*c;
}
inline void add_edge(int from,int to,int w)
{
edge[++num].nxt=head[from];
edge[num].to=to;
edge[num].w=w;
head[from]=num;
}
inline void add(int from,int to,int w)
{
add_edge(from,to,w);
add_edge(to,from,);
}
inline bool bfs()
{
memset(dep,,sizeof(dep));
queue<int> q;
while(!q.empty())
q.pop();
q.push(s);
dep[s]=;
while(!q.empty())
{
int u=q.front();
q.pop();
for(re int i=head[u];i!=-;i=edge[i].nxt)
{
int v=edge[i].to;
if(dep[v]==&&edge[i].w)
{
dep[v]=dep[u]+;
if(v==t)
return ;
q.push(v);
}
}
}
return ;
}
inline ll dfs(int u,ll dis)
{
if(u==t||!dis)
return dis;
ll diss=;
for(re int& i=cur[u];i!=-;i=edge[i].nxt)
{
int v=edge[i].to;
if(edge[i].w!=&&dep[v]==dep[u]+)
{
ll check=dfs(v,min(dis,edge[i].w));
if(check>)
{
dis-=check;
diss+=check;
edge[i].w-=check;
edge[i^].w+=check;
if(dis==) break;
}
}
}
return diss;
}
inline ll dinic()
{
ll ans=;
while(bfs())
{
for(re int i=s;i<=t;i++)
cur[i]=head[i];
while(ll d=dfs(s,inf))
ans+=d;
}
return ans;
}
int main()
{
//freopen("date.in","r",stdin);
memset(head,-,sizeof(head));
n=read();m=read();
for(re int i=;i<=n;i++)
for(re int j=;j<=m;j++){
a[i][j]=read();
h[i]=max(h[i],a[i][j]);
l[j]=max(l[j],a[i][j]);
if(a[i][j]) ans+=a[i][j]-;
}
s=,t=n+m+;
for(re int i=;i<=n;i++) if(h[i])ans-=h[i]-;
for(re int i=;i<=m;i++) if(l[i])ans-=l[i]-; for(re int i=;i<=n;i++)
for(re int j=;j<=m;j++){
if(h[i]==l[j]&&h[i]&&a[i][j]){
add(i,j+n,h[i]-);
}
}
for(re int i=;i<=n;i++){
if(!h[i]) continue;
add(s,i,h[i]-);
} for(re int i=;i<=m;i++){
if(!l[i]) continue;
add(i+n,t,l[i]-);
} cout<<ans+dinic();
return ;
}