Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom7月前

05/20
16:12
上下界网络流

[bzoj 3698] XWW的难题

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

XWW是个影响力很大的人,他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易,需要通过XWW的考核。
XWW给你出了这么一个难题:XWW给你一个N*N的正实数矩阵A,满足XWW性。
称一个N*N的矩阵满足XWW性当且仅当:(1)A[N][N]=0;(2)矩阵中每行的最后一个元素等于该行前N-1个数的和;(3)矩阵中每列的最后一个元素等于该列前N-1个数的和。
现在你要给A中的数进行取整操作(可以是上取整或者下取整),使得最后的A矩阵仍然满足XWW性。同时XWW还要求A中的元素之和尽量大。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个整数N,N ≤ 100。
接下来N行每行包含N个绝对值小于等于1000的实数,最多一位小数。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出一行,即取整后A矩阵的元素之和的最大值。无解输出No。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

129

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

【数据规模与约定】
有10组数据,n的大小分别为10,20,30...100。
【样例说明】
样例中取整后满足XWW性的和最大的矩阵为:
3 7 8 18
10 3 0 13
4 1 7 12
17 11 15 0

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

上下界网络流

(s, xi, a[n][i], a[n][i] + 1)

(yj, t, a[i][n], a[i][n] + 1)

(xi, yj, a[i][j], a[i][j] + 1)

跑一遍最大流

 

[bzoj 3698] XWW的难题