結果
問題 | No.1480 Many Complete Graphs |
ユーザー |
![]() |
提出日時 | 2021-04-16 20:50:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 207 ms / 2,000 ms |
コード長 | 895 bytes |
コンパイル時間 | 4,710 ms |
コンパイル使用メモリ | 266,264 KB |
最終ジャッジ日時 | 2025-01-20 19:07:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001int main(){int N,M;cin>>N>>M;mcf_graph<long long,long long> G(N+M*8);rep(_,M){int k;cin>>k;long long c;cin>>c;vector<int> s(k);rep(i,k)cin>>s[i];rep(i,k){G.add_edge(s[i]-1,N+8*_+(s[i]%2)*2,1,s[i]/2);G.add_edge(s[i]-1,N+8*_+(s[i]%2)*2+1,1,s[i]/2);G.add_edge(N+8*_+4+(s[i]%2),s[i]-1,1,s[i]/2);G.add_edge(N+8*_+4+(s[i]%2)+2,s[i]-1,1,s[i]/2);}G.add_edge(N+8*_+0,N+8*_+4+0,1,c);G.add_edge(N+8*_+1,N+8*_+4+1,1,c+1);G.add_edge(N+8*_+2,N+8*_+4+2,1,c+1);G.add_edge(N+8*_+3,N+8*_+4+3,1,c+1);}auto ans = G.flow(0,N-1,1);if(ans.first==0)cout<<-1<<endl;else cout<<ans.second<<endl;return 0;}