#P1313. 取整矩阵

    ID: 325 传统题 1000ms 512MiB 尝试: 85 已通过: 38 难度: 7 上传者: 标签>CF2200提高+/省选-向下取整与向上取整二分图建模上下界最大流下界转化超级源汇Dinic残量网络

取整矩阵

题目描述

给出一个实数矩阵,满足 Bi=第i行a数组元素之和.Ci=第i列a数组元素之和.

A11 A12 A13...A1n B1
A21 A22 A23...A2n B2
....................
An1 An2 An3...Ann Bn
C1  C2  C3....Cn  0

你现在需要对这个矩阵里的所有元素进取取上整或下整,要求仍然满足要求. 并且总和最大.

输入格式

第一行给出数字NN,N≤100N\leq 100 下面 NN 行 NN 列,给出数字矩阵,每个数字的值绝对值 ≤1000\leq 1000

输出格式

输出调整后矩阵元素和的最大值

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
129