#include using namespace std; using int64 = long long; /* * @title Dinic - Dinicフロー * @docs md/graph/Dinic.md */ template class Dinic { struct info { int to, rev; T cap; }; T ini, inf; vector> edge; vector level, iter; inline void bfs(int start) { for (int i = 0; i < level.size(); ++i) level[i] = -1; queue q; level[start] = 0; q.push(start); while (q.size()) { int from = q.front(); q.pop(); for (auto& e : edge[from]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[from] + 1; q.push(e.to); } } } } inline T dfs(int from, int goal, T flow) { if (from == goal) return flow; for (int& i = iter[from]; i < edge[from].size(); ++i) { auto& e = edge[from][i]; if (e.cap <= 0 || level[from] >= level[e.to]) continue; T dflow = dfs(e.to, goal, min(flow, e.cap)); if (dflow <= 0) continue; e.cap -= dflow; edge[e.to][e.rev].cap += dflow; return dflow; } return ini; } public: Dinic(int N, T ini, T inf) : edge(N), level(N), iter(N), ini(ini), inf(inf) { // do nothing } inline void make_edge(int from, int to, T cap) { edge[from].push_back({ to, (int)edge[to].size(), cap }); edge[to].push_back({ from, (int)edge[from].size() - 1, ini }); } inline T maxflow(int start, int goal) { T maxflow = ini; while (1) { bfs(start); if (level[goal] < 0) return maxflow; for (int i = 0; i < iter.size(); ++i) iter[i] = 0; T flow; while ((flow = dfs(start, goal, inf))>0) maxflow += flow; } } }; //verify https://atcoder.jp/contests/arc085/tasks/arc085_c /** * @url * @est */ int main() { cin.tie(0);ios::sync_with_stdio(false); int64 inf = 1e16; int H,W; cin >> H >> W; vector> grid(H,vector(W)); for(int i=0;i> grid[i][j]; vector R(H),C(W); for(int i=0;i> R[i]; for(int j=0;j> C[j]; //行/列に対して「植える」:0, 「植えない」:1 ,と割り当てる //加えて、問題の性質的にi行目に関してはフローを流す前に貪欲に選んでしまう //そうすることで、辺の数が2乗オーダーから落ちる Dinic di(H+W+2,0,inf); int S = H+W, G = H+W+1; int64 ans = 0; for(int i=0;i= 0) ans += R[i]-cost; //差分が負のとき→ iが0のとき|cost-R[i]|失う else di.make_edge(i,G,abs(R[i]-cost)); } for(int j=0;j