結果

問題 No.177 制作進行の宮森あおいです!
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-02 23:34:09
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,076 bytes
コンパイル時間 1,409 ms
コンパイル使用メモリ 169,516 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-04 01:27:33
合計ジャッジ時間 1,988 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 11 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void addEdge(int, int, int)’:
main.cpp:18:32: warning: narrowing conversion of ‘g[t].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   18 |         Edge a = { t, g[t].size(), 0, cap };
      |                       ~~~~~~~~~^~
main.cpp:19:32: warning: narrowing conversion of ‘g[s].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   19 |         Edge b = { s, g[s].size(), 0, cap };
      |                       ~~~~~~~~~^~

ソースコード

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

#include "bits/stdc++.h"
using namespace std;
const int maxnodes = 5000;
int nodes = maxnodes, src, dest;
int dist[maxnodes], q[maxnodes], work[maxnodes];
struct Edge {
int to, rev;
int f, cap;
};
vector<Edge> g[maxnodes];
// Adds bidirectional edge
void addEdge(int s, int t, int cap){
Edge a = { t, g[t].size(), 0, cap };
Edge b = { s, g[s].size(), 0, cap };
g[s].push_back(a);
g[t].push_back(b);
}
bool dinic_bfs() {
fill(dist, dist + nodes, -1);
dist[src] = 0;
int qt = 0;
q[qt++] = src;
for (int qh = 0; qh < qt; qh++) {
int u = q[qh];
for (int j = 0; j < (int)g[u].size(); j++) {
Edge &e = g[u][j];
int v = e.to;
if (dist[v] < 0 && e.f < e.cap) {
dist[v] = dist[u] + 1;
q[qt++] = v;
}
}
}
return dist[dest] >= 0;
}
int dinic_dfs(int u, int f) {
if (u == dest)
return f;
for (int &i = work[u]; i < (int)g[u].size(); i++) {
Edge &e = g[u][i];
if (e.cap <= e.f) continue;
int v = e.to;
if (dist[v] == dist[u] + 1) {
int df = dinic_dfs(v, min(f, e.cap - e.f));
if (df > 0) {
e.f += df;
g[v][e.rev].f -= df;
return df;
}
}
}
return 0;
}
int maxFlow(int _src, int _dest) {
src = _src;
dest = _dest;
int result = 0;
while (dinic_bfs()) {
fill(work, work + nodes, 0);
while (int delta = dinic_dfs(src, INT_MAX))
result += delta;
}
return result;
}
int main() {
int W;
cin >> W;
int N , M;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++)
{
cin >> v[i];
}
cin >> M;
nodes = N + M + 2;
for (int i = 0; i < N; i++)
{
addEdge(N + M, i, v[i]);
}
for (int i = 0; i < M; i++)
{
int C;
cin >> C;
addEdge(N + i, N + M + 1, C);
}
for (int i = 0; i < M; i++)
{
int Q;
cin >> Q;
set<int> s;
for (int j = 0; j < Q; j++)
{
int temp;
cin >> temp;
s.insert(temp);
}
for (int j = 0; j < N; j++)
{
if (!s.count(j)) continue;
addEdge(j, N + i, 999999);
}
}
int flow = maxFlow(N + M, N + M + 1);
//cout << flow << endl;
if (flow >= W) cout << "SHIROBAKO" << endl;
else cout << "BANSAKUTSUKITA" << endl;
//cin >> flow;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0