結果

問題 No.177 制作進行の宮森あおいです!
ユーザー koba-e964
提出日時 2017-02-07 00:34:10
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,606 bytes
コンパイル時間 1,303 ms
コンパイル使用メモリ 101,404 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 08:45:41
合計ジャッジ時間 2,490 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In instantiation of ‘void Dinic<T>::add_edge(int, int, T) [with T = int]’:
main.cpp:145:17:   required from here
main.cpp:92:58: warning: narrowing conversion of ‘(&((Dinic<int>*)this)->Dinic<int>::graph.std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::operator[](((std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::size_type)to)))->std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size()’ from ‘std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   92 |     graph[from].push_back((edge) {to, cap, graph[to].size()});
      |                                            ~~~~~~~~~~~~~~^~
main.cpp:93:61: warning: narrowing conversion of ‘((&((Dinic<int>*)this)->Dinic<int>::graph.std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::operator[](((std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::size_type)from)))->std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size() - 1)’ from ‘std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   93 |     graph[to].push_back((edge) {from, 0, graph[from].size() - 1});
      |                                          ~~~~~~~~~~~~~~~~~~~^~~

ソースコード

diff #
プレゼンテーションモードにする

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
/**
* Dinic's algorithm for maximum flow problem.
* Header requirement: vector, queue
* Verified by: ABC010-D(http://abc010.contest.atcoder.jp/submissions/602810)
* ARC031-D(http://arc031.contest.atcoder.jp/submissions/1050071)
* POJ 3155(http://poj.org/problem?id=3155)
*/
template<class T = int>
class Dinic {
private:
struct edge {
int to;
T cap;
int rev; // rev is the position of reverse edge in graph[to]
};
std::vector<std::vector<edge> > graph;
std::vector<int> level;
std::vector<int> iter;
/* Perform bfs and calculate distance from s */
void bfs(int s) {
level.assign(level.size(), -1);
std::queue<int> que;
level[s] = 0;
que.push(s);
while (! que.empty()) {
int v = que.front(); que.pop();
for (int i = 0; i < graph[v].size(); ++i) {
edge &e = graph[v][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
/* search augment path by dfs.
if f == -1, f is treated as infinity. */
T dfs(int v, int t, T f) {
if (v == t) {
return f;
}
for (int &i = iter[v]; i < graph[v].size(); ++i) {
edge &e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
T newf = f == -1 ? e.cap : std::min(f, e.cap);
T d = dfs(e.to, t, newf);
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
public:
/* v is the number of vertices (labeled from 0 .. v-1) */
Dinic(int v) : graph(v), level(v, -1), iter(v, 0) {}
void add_edge(int from, int to, T cap) {
graph[from].push_back((edge) {to, cap, graph[to].size()});
graph[to].push_back((edge) {from, 0, graph[from].size() - 1});
}
T max_flow(int s, int t) {
T flow = 0;
while (1) {
bfs(s);
if (level[t] < 0) {
return flow;
}
iter.assign(iter.size(), 0);
T f;
while ((f = dfs(s, t, -1)) > 0) {
flow += f;
}
}
}
std::pair<T,std::vector<int> > max_flow_cut(int s, int t) {
T flow = 0;
while (1) {
bfs(s);
if (level[t] < 0) {
std::vector<int> ret;
for (int i = 0; i < graph.size(); ++i) {
if (level[i] < 0) {
ret.push_back(i);
}
}
return std::pair<T, std::vector<int> >(flow, ret);
}
iter.assign(iter.size(), 0);
T f;
while ((f = dfs(s, t, -1)) > 0) {
flow += f;
}
}
}
};
int main(void){
int w, n;
cin >> w >> n;
VI j(n);
REP(i, 0, n) { cin >> j[i]; }
int m;
cin >> m;
VI c(m);
REP(i, 0, m) { cin >> c[i]; }
Dinic<int> din(n + m + 2);
REP(i, 0, n) {
din.add_edge(0, 2 + i, j[i]);
}
REP(i, 0, m) {
din.add_edge(2 + n + i, 1, c[i]);
}
REP(i, 0, m) {
int qi;
cin >> qi;
VI lim(n, 1e8);
REP(j, 0, qi) {
int x;
cin >> x;
x--;
lim[x] = 0;
}
REP(j, 0, n) {
din.add_edge(2 + j, 2 + n + i, lim[j]);
}
}
cout << (din.max_flow(0, 1) >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0