jubeeeeeat（网络流）

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数。

样例输入

样例输出

提示

【数据说明】
对于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

输出没有换行符。。。

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 
 6 const int INF = 1e9;
 7 const int N = 100100;
 8 
 9 struct Edge{
10     int to,nxt,c;
11 }e[N];
12 int q[500100],head[N],cur[N],dis[N],mp[50][50];
13 int S,T,L,R,tot=1,tn;
14 
15 inline char nc() {
16     static char buf[100000],*p1 = buf,*p2 = buf;
17     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
18 }
19 inline int read() {
20     int x = 0,f = 1;char ch = nc();
21     for (; ch<'0'||ch>'9'; ch = nc()) if (ch=='-') f = -1;
22     for (; ch>='0'&&ch<='9'; ch = nc()) x = x * 10 + ch - '0';
23     return x * f;
24 }
25 inline void add_edge(int u,int v,int w) {
26     e[++tot].to = v,e[tot].c = w,e[tot].nxt = head[u],head[u] = tot;
27     e[++tot].to = u,e[tot].c = 0,e[tot].nxt = head[v],head[v] = tot;
28 }
29 inline bool bfs() {
30     for (int i=1; i<=tn; ++i) {
31         cur[i] = head[i];dis[i] = -1;
32     }
33     L = 1;R = 0;
34     q[++R] = S;dis[S] = 0;
35     while (L <= R) {
36         int u = q[L++];
37         for (int i=head[u]; i; i=e[i].nxt) {
38             int v = e[i].to,c = e[i].c;
39             if (dis[v]==-1 && c > 0) {
40                 dis[v] = dis[u] + 1;
41                 q[++R] = v;
42                 if (v == T) return true;
43             }
44         }
45     }
46     return false;
47 }
48 int dfs(int u,int flow) {
49     if (u==T) return flow;
50     int used = 0;
51     for (int &i=cur[u]; i; i=e[i].nxt) {
52         int v = e[i].to,c = e[i].c;
53         if (dis[v]==dis[u]+1 && c>0) {
54             int tmp = dfs(v,min(c,flow-used));
55             if (tmp > 0) {
56                 e[i].c -= tmp;e[i^1].c += tmp;
57                 used += tmp;
58                 if (used==flow) break;
59             }
60         }
61     }
62     if (used != flow) dis[u] = -1;
63     return used;
64 }
65 inline int dinic() {
66     int ans = 0;
67     while (bfs()) ans += dfs(S,INF);
68     return ans;
69 }
70 int main() {
71     int n = read(),m = read(),h = read(),cnt = 0;
72     tn = n*n+m+2;
73     S = tn-1,T = tn;
74     for (int i=1; i<=n; ++i) 
75         for (int j=1; j<=n; ++j)
76             mp[i][j] = read();
77     for (int i=1; i<=m; ++i) add_edge(S,i,5);
78     for (int a,b,c,k=1; k<=m; ++k) {
79         a = read(),b = read(),c = read();
80         for (int i=a; i<(a+c); ++i) 
81             for (int j=b; j<(b+c); ++j) 
82                 if (mp[i][j]) add_edge(k,(i-1)*n+j+m,1);
83     }
84     for (int i=1; i<=n; ++i) 
85         for (int j=1; j<=n; ++j)
86             if (mp[i][j]) cnt++,add_edge((i-1)*n+j+m,T,1);
87     int tmp = dinic();
88     printf("%d",min(tmp+h,cnt));    
89     return 0;
90 }