結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
![]() |
提出日時 | 2015-04-02 23:48:25 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,743 bytes |
コンパイル時間 | 632 ms |
コンパイル使用メモリ | 86,824 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 01:28:32 |
合計ジャッジ時間 | 1,256 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int)’: main.cpp:35:53: warning: narrowing conversion of ‘G[to].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘ll’ {aka ‘long long int’} [-Wnarrowing] 35 | G[from].push_back((edge){to, cap, G[to].size()}); | ~~~~~~~~~~^~ main.cpp:36:57: warning: narrowing conversion of ‘(G[from].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘ll’ {aka ‘long long int’} [-Wnarrowing] 36 | G[to].push_back((edge){from, cap, G[from].size()-1}); | ~~~~~~~~~~~~~~^~
ソースコード
#include <algorithm>#include <climits>#include <cmath>#include <cstdio>#include <cstdlib>#include <ctime>#include <iostream>#include <sstream>#include <functional>#include <map>#include <string>#include <cstring>#include <vector>#include <queue>#include <stack>#include <deque>#include <set>#include <list>#include <numeric>using namespace std;const double PI = 3.14159265358979323846;const double EPS = 1e-12;const int INF = 1<<25;typedef pair<int,int> P;typedef long long ll;typedef unsigned long long ull;#define V 110struct edge{ll to, cap, rev;};vector<edge> G[V];bool used[V];void add_edge(int from, int to, int cap){G[from].push_back((edge){to, cap, G[to].size()});G[to].push_back((edge){from, cap, G[from].size()-1});}ll dfs(int v, int t, ll f){if(v==t) return f;used[v] = true;for(int i = 0; i < G[v].size(); i++){edge &e = G[v][i];if(!used[e.to] && e.cap > 0){ll d = dfs(e.to, t, min(f, e.cap));if(d>0){e.cap -= d;G[e.to][e.rev].cap += d;return d;}}}return 0;}ll max_flow(int s, int t){ll flow = 0;while(1){memset(used, 0, sizeof(used));ll f = dfs(s, t, INF);if(f==0) return flow;flow += f;}}bool bad[V][V];int main(){ll w, n, m, s = V-2, t = V-1;cin>>w>>n;for(int i = 0; i < n; i++){int a;cin>>a;add_edge(s, i, a);}cin>>m;for(int i = 0; i < m; i++){int a;cin>>a;add_edge(n+i, t, a);}for(int i = 0; i < m; i++){int q;cin>>q;for(int j = 0; j < q; j++){int a;cin>>a;bad[a-1][i] = true;}}for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(!bad[i][j]) add_edge(i, n+j, INF);cout<<(max_flow(s, t)>=w?"SHIROBAKO":"BANSAKUTSUKITA")<<endl;return 0;}