Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

02/7
13:21
图论 网络流

jubeeeeeat 网络流-最大流

描述

众所周知,LZF很喜欢打一个叫Jubeat的游戏。这是个音乐游戏,游戏界面是4×4的方阵,会根据音乐节奏要求玩家按下一些指定方块(以下称combo)。LZF觉得这太简单了,于是自己仿了个游戏叫Jubeeeeeat,唯一不同之处就是界面大小,Jubeeeeeat的界面为n×n的方阵。 在某一刻,界面同时出现了若干个combo。LZF终于觉得有些困难了,但毕竟LZF不是普通人,他有很多只手。LZF的手分为m只“肉质手”和q只“意念手”。顾名思义,“肉质手”是实际存在的手,每只肉质手都有5根手指,每根手指能按一个combo,但每只手的速度都不同,受限于此,LZF的每只肉质手的控制范围是一个固定大小的正方形。“意念手”即虚无之手,每只手只有1根手指,但控制范围为全局。 现在LZF想知道,他最多能按下多少个combo。

输入

输入文件名为 jubeeeeeat.in。 第1行输入三个正整数n,m,q。 接下来是一个n×n的01矩阵,描述combo的位置,1为combo。 最后m行每行三个正整数xi,yi,ai,分别表示第i只肉质手掌控区域左上方块的行、列和边长。(行、列从1数起)

输出

输出文件名为 jubeeeeeat.out。 输出一个正整数,表示最多能按下的combo数。

样例输入

3 1 3
1 0 1
1 1 1
1 0 1
1 1 2

样例输出

6

提示

【数据说明】 对于20%的数据,n=5,m=2,q=2; 对于50%的数据,1≤n≤20,1≤m, q≤50; 对于100%的数据,1≤n≤40,1≤m, q≤300,1≤xi, yi≤n,1≤xi+ai-1, yi+ai-1≤n。

Solution

一个非常裸的最大流。将肉质手向控制区域内的combo连边,流量为1,意志手向所有的combo连边,流量为1.源点向肉质手连流量为5的边,向意志手连流量为1的边,所有的combo与汇点连流量为1的边。