結果
問題 | No.957 植林 |
ユーザー |
|
提出日時 | 2019-12-27 09:57:54 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 624 ms / 2,000 ms |
コード長 | 2,397 bytes |
コンパイル時間 | 470 ms |
コンパイル使用メモリ | 47,488 KB |
実行使用メモリ | 12,096 KB |
最終ジャッジ日時 | 2024-10-07 06:56:09 |
合計ジャッジ時間 | 15,375 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:77:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 77 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:78:72: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 78 | for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%lld", &g[i][j]); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:79:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 79 | for (int i = 1; i <= n; i++) scanf("%lld", &r[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:80:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 80 | for (int i = 1; i <= m; i++) scanf("%lld", &c[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <vector> #include <queue> using namespace std; #define PB push_back constexpr int kN = int(1E5 + 10), kNN = int(3E2 + 10); constexpr long long int kInf = (long long int) (1E16 + 10); struct Edge { int to, rev; long long int cap; }; vector<Edge> graph[kN]; int dep[kN], went[kN], iter[kN]; void AddEdge(int u, int v, long long int c) { graph[u].PB({v, int(graph[v].size()), c}); graph[v].PB({u, int(graph[u].size()) - 1, 0}); return ; } void bfs(int s, int t) { int nxt; queue<int> q; q.push(s); iter[s] = dep[s] = 0; went[s] = t; while (!q.empty()) { nxt = q.front(); q.pop(); for (Edge i : graph[nxt]) if (went[i.to] != t && i.cap > 0) { q.push(i.to); went[i.to] = t; dep[i.to] = dep[nxt] + 1; iter[i.to] = 0; } } return ; } long long int dfs(int u, int t, long long int nv) { if (u == t) return nv; int temp; for (int &i = iter[u]; i < int(graph[u].size()); i++) { Edge& nxt = graph[u][i]; if (nxt.cap > 0 && dep[nxt.to] > dep[u]) { temp = dfs(nxt.to, t, min(nv, nxt.cap)); if (temp > 0) { nxt.cap -= temp; graph[nxt.to][nxt.rev].cap += temp; return temp; } } } return 0; } long long int dinic(int s, int t) { long long int ans = 0, f; int cnt = 0; for (int i = 0; i < kN; i++) went[i] = cnt; while (true) { bfs(s, ++cnt); if (went[s] != went[t]) break; while ((f = dfs(s, t, kInf)) > 0) ans += f; } return ans; } long long int a[kNN], g[kNN][kNN], r[kNN], c[kNN]; int main() { int n, m, s, t; long long int ans = 0, tmp; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%lld", &g[i][j]); for (int i = 1; i <= n; i++) scanf("%lld", &r[i]); for (int i = 1; i <= m; i++) scanf("%lld", &c[i]); s = 0; t = n + m + 1; for (int i = 1; i <= n; i++) a[i] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i] += g[i][j]; for (int i = 1; i <= n; i++) { tmp = min(r[i], a[i]); r[i] -= tmp; a[i] -= tmp; } for (int i = 1; i <= n; i++) ans += r[i]; for (int i = 1; i <= m; i++) ans += c[i]; for (int i = 1; i <= n; i++) AddEdge(s, i, a[i]); for (int i = 1; i <= m; i++) AddEdge(i + n, t, c[i]); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) AddEdge(i, j + n, g[i][j]); printf("%lld\n", ans - dinic(s, t)); }