Description那是春日里一个天气晴朗的好日子,你准备去见见你的老朋友Patrick,也是你之前的犯罪同伙。Patrick在编程竞赛上豪赌输掉了一大笔钱,所以他需要再干一票。 Description 那是春日里一
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
样例15 51 4 0 5 22 1 2 0 10 2 3 4 40 3 0 3 11 2 2 1 1样例22 350 20 320 10 3Sample Output
样例19样例230 思路：一开始考虑，每个不为0的位置都拿到1，然后每行每列最大值不能动。然后又考虑到，如果行列最大值相同，我们可以在他们交叉的位置放一个最大值即可，而不需要两个。因此转化成一个二分图匹配的问题。（显然不同的最大值不会互相干扰，因为之间根本不可能有边）每成功匹配到一个，就可以多拿一个最大值。
1 #include 2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R i=a;i=b;i--) 6 #define rp(i,x) for(R i=H[x];i!=-1;i=E[i].nt) 7 #define ms(i,a) memset(a,i,sizeof(a)) 8 #define gc() getchar() 9 #define LL long long 10 templatevoid read(T char c=0; 12 while (!isdigit(c)) c=gc(); 13 while (isdigit(c)) x=x*10+(c^48),c=gc(); 14 }15 int const N=110; 16 struct Edge{17 int to,nt; 18 }E[N*N]; 19 int n,m,H[N],cnt,vis[N],lk[N],a[N][N],r[N],c[N]; 20 LL ans; 21 void add(int a,int b){22 E[cnt]=(Edge){b,H[a]}; H[a]=cnt++; 23 }24 int find(int x){25 rp(i,x){26 int v=E[i].to; 27 if(vis[v]) continue ; 28 vis[v]=1; 29 if(!lk[v] || find(lk[v])){30 lk[v]=x; return 1; 31 }32 }33 return 0; 34 }35 int main(){36 read(n);read(m); 37 rep(i,1,n) rep(j,1,m){38 read(a[i][j]); 39 if(a[i][j]) ans+=a[i][j]-1; 40 r[i]=max(r[i],a[i][j]); 41 c[j]=max(c[j],a[i][j]); 42 } 43 rep(i,1,n) if(r[i]) ans-=r[i]-1; 44 rep(i,1,m) if(c[i]) ans-=c[i]-1; 45 ms(-1,H); 46 rep(i,1,n) rep(j,1,m) if(r[i]==c[j] 47 rep(i,1,n){48 ms(0,vis); 49 if(find(i)) ans+=r[i]-1; 50 }51 cout