OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

@OceanEye7年前

06/10
13:56
OI

BZOJ3698

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

朴素的建图,只是跑的网络流模式变了

然后就可以随便艹了

 

BZOJ3698

@OceanEye7年前

05/31
18:52
OI

有上下界网络流的学习笔记

Link1   Link2

 

BZOJ3876

BZOJ2502

 

BZOJ2055

 

 

有上下界网络流的学习笔记

@OceanEye7年前

05/9
21:15
OI

BZOJ4808

题目名字很有趣

但是看完题面会发现这就是个黑白染色最小割

网络流大法好,ISAP直接跑

好像这几道题是一个系列的233

 

BZOJ4808

@OceanEye7年前

05/2
20:04
OI

BZOJ1324

有些炸裂的题解

题目是一道最大点独立集,比较裸的那种

最大点独立集=最小点覆盖集的补集

然后套最小点覆盖集用sum-tot_flow即可

 

BZOJ1324

@OceanEye7年前

04/28
23:34
OI

BZOJ1497

最小割

从源点向每个人连收益大小的边

人向站连大小为INF的边

站向汇连大小为成本的边

这个时候的割有三种情况:

1.把收益割掉了,此时支出>收入

2.把支出割掉了,此时支出<收入

3.支出和收入同时割掉了,支出=收入

总的答案就是sum-割

 

BZOJ1497

@OceanEye7年前

04/8
00:03
OI

BZOJ1834

嘛……几万年没好好写过网络流了……
gap优化真的强,把我的1s的代码降成了0.05s
相信前面榜上的就是gap的吧……

BZOJ1834