jubeeeeeat
- 总时间限制:
- 1000ms
- 内存限制:
- 256000kB
描述
众所周知，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。
code
输出没有换行符。。。
#include<cstdio>
#include<algorithm> using namespace std; const int INF = 1e9;
const int N = ; struct Edge{
int to,nxt,c;
}e[N];
int q[],head[N],cur[N],dis[N],mp[][];
int S,T,L,R,tot=,tn; inline char nc() {
static char buf[],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
int x = ,f = ;char ch = nc();
for (; ch<''||ch>''; ch = nc()) if (ch=='-') f = -;
for (; ch>=''&&ch<=''; ch = nc()) x = x * + ch - '';
return x * f;
}
inline void add_edge(int u,int v,int w) {
e[++tot].to = v,e[tot].c = w,e[tot].nxt = head[u],head[u] = tot;
e[++tot].to = u,e[tot].c = ,e[tot].nxt = head[v],head[v] = tot;
}
inline bool bfs() {
for (int i=; i<=tn; ++i) {
cur[i] = head[i];dis[i] = -;
}
L = ;R = ;
q[++R] = S;dis[S] = ;
while (L <= R) {
int u = q[L++];
for (int i=head[u]; i; i=e[i].nxt) {
int v = e[i].to,c = e[i].c;
if (dis[v]==- && c > ) {
dis[v] = dis[u] + ;
q[++R] = v;
if (v == T) return true;
}
}
}
return false;
}
int dfs(int u,int flow) {
if (u==T) return flow;
int used = ;
for (int &i=cur[u]; i; i=e[i].nxt) {
int v = e[i].to,c = e[i].c;
if (dis[v]==dis[u]+ && c>) {
int tmp = dfs(v,min(c,flow-used));
if (tmp > ) {
e[i].c -= tmp;e[i^].c += tmp;
used += tmp;
if (used==flow) break;
}
}
}
if (used != flow) dis[u] = -;
return used;
}
inline int dinic() {
int ans = ;
while (bfs()) ans += dfs(S,INF);
return ans;
}
int main() {
int n = read(),m = read(),h = read(),cnt = ;
tn = n*n+m+;
S = tn-,T = tn;
for (int i=; i<=n; ++i)
for (int j=; j<=n; ++j)
mp[i][j] = read();
for (int i=; i<=m; ++i) add_edge(S,i,);
for (int a,b,c,k=; k<=m; ++k) {
a = read(),b = read(),c = read();
for (int i=a; i<(a+c); ++i)
for (int j=b; j<(b+c); ++j)
if (mp[i][j]) add_edge(k,(i-)*n+j+m,);
}
for (int i=; i<=n; ++i)
for (int j=; j<=n; ++j)
if (mp[i][j]) cnt++,add_edge((i-)*n+j+m,T,);
int tmp = dinic();
printf("%d",min(tmp+h,cnt));
return ;
}