Noi模拟 矩阵 二分 上下界网络流

矩阵(mat)

【题目描述】

给定一个整数矩阵A[n*m],求一个整数矩阵B[n*m],满足,最小化。

输出任意一组合法解即可。

【输入数据】

第一行两个数n、m,表示矩阵的大小。

接下来n行,每行m个整数,描述矩阵A。

最后一行两个整数L,R。

【输出数据】

第一行,输出最小的答案;

接下来输出n行,m列,描述矩阵B。

【样例输入】

2 2

0 1

2 1

0 1

【样例输出】

1

1 1

1 1

【数据范围】

对于20%的数据满足n,m<=20;

对于另外20%的数据满足0<=L<=R<=1;

对于100%的数据满足n,m<=200,0<=L<=R<=1000,0<=Aij<=1000。

///////////////////////////////////////////////////////////////////////////////////

考场上就想到了应该是二分+上下界网络流,然而构造了半天图也没构造出来。考完试,dev-xys就跟我谈笑风生,讲出了T1的建图方式,真是太神了,感觉自己完全想不到,这种建图方式竟然是用边来表示原图的点,太神了!!!!!

///////////////////////////////////////////////////////////////////////////////////

我们先二分一个答案,注意下,别[0,1000],最后答案可能是1000*200呢。

然后我们讲一下,建图,我们搞一个源点,搞一个汇点,然后对于行建立点,对于列建立点,然后我们源点连行,列连汇点。然后每个行都跟一个列连,比如i->j,那么这条边就代表a[i][j]这个点。

我们不是二分了一个答案Mid么。那么显然行的范围是max(0,u[i] – x) – > u[i] + x,列的范围是max(0,v[i] – x) -> v[i] + x,那源汇与之相连的边的上下界就是这个。其余代表点的的边的范围是[l,r]。对吧,那上下界网络流一下就好。

好久没写上下界网络流了,再回顾一下吧。

我们考虑原图,我们先强制把下界流满,记录再这个情况下,每个点的入流和出流。显然最后每个点的入流和出流显然要相等才对。那么我们对于入流较多的点,我们再建立一个超级源流过来,模拟必须要流的流量,流量为出入之差绝对值。对于出流较多的点,我们再建立一个超级汇,从这个点连到超级汇,模拟必须流出的流量,流量为出入之差绝对值。因为我们是在盼是否有流法,所以要从原图的汇流到源一条inf的边,然后就OK啦。

详细见代码。

发表评论