結果
問題 | No.1541 ゅゅさんのテスト勉強 |
ユーザー |
![]() |
提出日時 | 2021-05-23 04:03:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 1,781 bytes |
コンパイル時間 | 1,365 ms |
コンパイル使用メモリ | 99,812 KB |
最終ジャッジ日時 | 2025-01-21 17:31:40 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include<iostream> #include<vector> #include<atcoder/maxflow> struct input_structure{ int n; long long m; std::vector<int> k; std::vector<std::vector<int>> A; std::vector<std::vector<long long>> B; std::vector<long long> C; input_structure(){ std::cin >> n >> m; k.resize(n); A.resize(n); B.resize(n); C.resize(n); for(int i=0;i<n;i++){ std::cin >> k[i] >> C[i]; A[i].resize(k[i]); B[i].resize(k[i]); for(int j=0;j<k[i];j++)std::cin >> A[i][j]; for(int j=0;j<k[i];j++)std::cin >> B[i][j]; } } friend std::ostream& operator<<(std::ostream &os,input_structure &in){ std::cout << in.n << ' ' << in.m << '\n'; for(int i=0;i<in.n;i++){ std::cout << in.k[i] << ' ' << in.C[i] << '\n'; for(auto x:in.A[i])std::cout << x << ' '; std::cout << '\n'; for(auto x:in.B[i])std::cout << x << ' '; std::cout << '\n'; } return os; } }; //想定解 フローやるだけ. long long solve_assumed(input_structure in){ for(auto &vec:in.A)for(int &idx:vec)idx--; long long sum=in.m*in.n; for(int i=0;i<in.n;i++)for(int j=0;j<in.k[i];j++){ sum+=in.B[i][j]; } atcoder::mf_graph<long long> g(in.n+2); for(int i=0;i<in.n;i++){ g.add_edge(in.n,i,in.C[i]); long long now_cost=in.m; for(int j=0;j<in.k[i];j++)now_cost+=in.B[i][j]; g.add_edge(i,in.n+1,now_cost); for(int j=0;j<in.k[i];j++){ g.add_edge(in.A[i][j],i,in.B[i][j]); } } return sum-g.flow(in.n,in.n+1); } int main(){ input_structure in; std::cout << solve_assumed(in) << '\n'; }