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
題解
我們把每一個都取成高度為1。然後放回每一行每一列的最大高度。
如果i行與j列最大高度相同，則有可能放在[i,j]使得隻需放回一個最大值，但要滿足[i,j]之前放有箱子。
代碼
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
#define mod 10000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*+ch-'0';ch=getchar();}
return x*f;
}
ll ans;
int n,m,mxn[],mxm[],flag[],match[],T,a[][];
vector<int>e[];
bool find(int now)
{
for (int i=;i<e[now].size();i++)
{
if (flag[e[now][i]]==T) continue;
flag[e[now][i]]=T;
if (!match[e[now][i]]||find(match[e[now][i]]))
{
match[e[now][i]]=now;
return ;
}
}
return ;
}
int main()
{
n=read();m=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
a[i][j]=read();if (a[i][j]) ans+=a[i][j]-;
mxn[i]=max(mxn[i],a[i][j]);mxm[j]=max(mxm[j],a[i][j]);
}
for (int i=;i<=n;i++) if (mxn[i]) ans-=mxn[i]-;
for (int i=;i<=m;i++) if (mxm[i]) ans-=mxm[i]-;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)if (mxn[i]==mxm[j]&&a[i][j])e[i].push_back(j);
for (int i=;i<=n;i++)
{
T=i;if (find(i)) ans+=mxn[i]-;
}
cout<<ans;
return ;
}