結果
問題 | No.1541 ゅゅさんのテスト勉強 |
ユーザー |
![]() |
提出日時 | 2021-06-06 18:22:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 1,996 bytes |
コンパイル時間 | 1,951 ms |
コンパイル使用メモリ | 181,196 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-23 02:46:50 |
合計ジャッジ時間 | 3,147 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long INF = 10000000000000000;template <typename Cap>struct ford_fulkerson{struct edge{int to, rev;Cap cap;edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap){}};int N;vector<vector<edge>> G;ford_fulkerson(){}ford_fulkerson(int N): N(N), G(N){}void add_edge(int from, int to, Cap cap){int id1 = G[from].size();int id2 = G[to].size();G[from].push_back(edge(to, id2, cap));G[to].push_back(edge(from, id1, 0));}Cap max_flow(int s, int t){Cap flow = 0;while (1){vector<Cap> m(N, INF);vector<int> pv(N, -1);vector<int> pe(N, -1);vector<bool> used(N, false);queue<int> Q;Q.push(s);used[s] = true;while (!Q.empty()){int v = Q.front();Q.pop();int cnt = G[v].size();for (int i = 0; i < cnt; i++){int w = G[v][i].to;if (!used[w] && G[v][i].cap > 0){used[w] = true;m[w] = min(m[v], G[v][i].cap);pv[w] = v;pe[w] = i;Q.push(w);}}}if (!used[t]){break;}Cap f = m[t];for (int i = t; i != s; i = pv[i]){G[pv[i]][pe[i]].cap -= f;G[i][G[pv[i]][pe[i]].rev].cap += f;}flow += f;}return flow;}};int main(){int N, M;cin >> N >> M;vector<long long> S(N, M);ford_fulkerson<long long> G(N + 2);for (int i = 0; i < N; i++){int k, C;cin >> k >> C;S[i] -= C;vector<int> A(k);for (int j = 0; j < k; j++){cin >> A[j];A[j]--;}vector<int> B(k);for (int j = 0; j < k; j++){cin >> B[j];}for (int j = 0; j < k; j++){S[A[j]] += B[j];G.add_edge(i, A[j], B[j]);}}long long ans = 0;for (int i = 0; i < N; i++){if (S[i] > 0){ans += S[i];G.add_edge(N, i, 0);G.add_edge(i, N + 1, S[i]);} else {G.add_edge(N, i, -S[i]);G.add_edge(i, N + 1, 0);}}cout << ans - G.max_flow(N, N + 1) << endl;}