http://cdqz.openjudge.cn/2016/0003/
shabi建图,shabi网络流
#include <bits/stdc++.h> #include <queue> using namespace std; const int N = 3010; const int M = 5e5 + 10; #define gc getchar() #define oo 999999999 int n, m, p, now, S, T; int dis[N], head[N], now_head[N]; bool H[N][N]; int B[N][N]; struct Node{ int u, v, cap, nxt; }G[M]; queue <int> Q; inline int read(){ int x = 0, f = 1; char c = gc; while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x * f; } inline void add(int u, int v, int cap){ G[now].v = v; G[now].cap = cap; G[now].nxt = head[u]; head[u] = now ++; } inline bool bfs(){ for(int i = S; i <= T; i ++) dis[i] = -1, now_head[i] = head[i]; dis[S] = 0; while(!Q.empty()) Q.pop(); Q.push(S); while(!Q.empty()){ int topp = Q.front(); Q.pop(); for(int i = head[topp]; ~ i; i = G[i].nxt){ int v = G[i].v; if(dis[v] == -1 && G[i].cap > 0){ dis[v] = dis[topp] + 1; if(v == T) return 1; Q.push(v); } } } return 0; } int dfs(int now, int flow){ if(now == T) return flow; int f, ret = 0; for(int & i = now_head[now]; ~ i; i = G[i].nxt){ int v = G[i].v; if(dis[v] == dis[now] + 1 && G[i].cap > 0){ f = dfs(v, min(G[i].cap, flow - ret)); if(f){ G[i].cap -= f; G[i ^ 1].cap += f; ret += f; if(ret == flow) break; } } } if(ret != flow) dis[now] = -1; return ret; } inline int Dinic(){ int answer = 0; while(bfs()) answer += dfs(S, oo); return answer; } inline void add_I(int x, int y, int l, int u){ for(int i = x; i <= x + l - 1; i ++) for(int j = y; j <= y + l - 1; j ++) if(H[i][j]) add(u, B[i][j], 1), add(B[i][j], u, 0); } inline void build(){ for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) if(H[i][j]) add(B[i][j], T, 1), add(T, B[i][j], 0); for(int i = 1; i <= m; i ++){ int x = read(), y = read(), z = read(); add_I(x, y, z, i); } for(int i = 1; i <= m; i ++) add(0, i, 5), add(i, 0, 0); } int main() { n = read(); m = read(); p = read(); T = m; int js(0); for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { H[i][j] = read(); if(H[i][j]) js ++, B[i][j] = T + 1, T ++; } T ++, S = 0; for(int i = 0; i <= T; i ++) head[i] = -1; build(); int ans = Dinic(); int answer = min(js, ans + p); cout << answer; return 0; } /* 3 1 3 1 0 1 1 1 1 1 0 1 1 1 2 */