Submission #8755633
Source Code Expand
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
// dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
struct IOSetup {
IOSetup() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(20);
cerr << fixed << setprecision(10);
}
} iosetup;
/*-------------------------------------------------*/
template <typename T, typename U>
struct PrimalDual {
using Pui = pair<U, int>;
struct Edge {
int dst, rev;
T cap;
U cost;
Edge(int dst, T cap, U cost, int rev) : dst(dst), cap(cap), cost(cost), rev(rev) {}
};
vector<vector<Edge> > graph;
PrimalDual(int n, T TINF, U UINF) : n(n), TINF(TINF), UINF(UINF), graph(n), prev_v(n, -1), prev_e(n, -1), potential(n, 0), dist(n) {}
void add_edge(int src, int dst, T cap, U cost) {
graph[src].emplace_back(dst, cap, cost, graph[dst].size());
graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
}
U minimum_cost_flow(int s, int t, T flow) {
U res = 0;
// bellman_ford(s);
// if (dist[t] == UINF) return UINF;
// res += calc(s, t, flow);
while (flow > 0) {
dijkstra(s);
if (dist[t] == UINF) return UINF;
res += calc(s, t, flow);
}
return res;
}
U minimum_cost_flow(int s, int t) {
U res = 0;
bellman_ford(s);
if (potential[t] >= 0 || dist[t] == UINF) return res;
T tmp = TINF;
res += calc(s, t, tmp);
while (true) {
dijkstra(s);
if (potential[t] >= 0 || dist[t] == UINF) return res;
res += calc(s, t, tmp);
}
// TINF - tmp
}
pair<T, U> min_cost_max_flow(int s, int t, T flow) {
T mx = flow;
U cost = 0;
// bellman_ford(s);
// if (dist[t] == UINF) return {mx - flow, cost};
// cost += calc(s, t, flow);
while (flow > 0) {
dijkstra(s);
if (dist[t] == UINF) return {mx - flow, cost};
cost += calc(s, t, flow);
}
return {mx - flow, cost};
}
private:
int n;
T TINF;
U UINF;
vector<int> prev_v, prev_e;
vector<U> potential, dist;
priority_queue<Pui, vector<Pui>, greater<Pui> > que;
void bellman_ford(int s) {
fill(ALL(dist), UINF);
dist[s] = 0;
bool is_updated = true;
REP(step, n) {
is_updated = false;
REP(i, n) if (dist[i] != UINF) {
REP(j, graph[i].size()) {
Edge e = graph[i][j];
if (e.cap > 0 && dist[e.dst] > dist[i] + e.cost) {
dist[e.dst] = dist[i] + e.cost;
prev_v[e.dst] = i;
prev_e[e.dst] = j;
is_updated = true;
}
}
}
if (!is_updated) break;
}
if (is_updated) assert(false);
REP(i, n) {
if (dist[i] != UINF) potential[i] += dist[i];
}
}
void dijkstra(int s) {
fill(ALL(dist), UINF);
dist[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
Pui pr = que.top(); que.pop();
int ver = pr.second;
if (dist[ver] < pr.first) continue;
REP(i, graph[ver].size()) {
Edge e = graph[ver][i];
U nx = dist[ver] + e.cost + potential[ver] - potential[e.dst];
if (e.cap > 0 && dist[e.dst] > nx) {
dist[e.dst] = nx;
prev_v[e.dst] = ver;
prev_e[e.dst] = i;
que.emplace(dist[e.dst], e.dst);
}
}
}
REP(i, n) {
if (dist[i] != UINF) potential[i] += dist[i];
}
}
U calc(int s, int t, T &flow) {
T f = flow;
for (int v = t; v != s; v = prev_v[v]) f = min(f, graph[prev_v[v]][prev_e[v]].cap);
flow -= f;
for (int v = t; v != s; v = prev_v[v]) {
Edge &e = graph[prev_v[v]][prev_e[v]];
e.cap -= f;
graph[v][e.rev].cap += f;
}
return f * potential[t];
}
};
int main() {
int n, m, d; cin >> n >> m >> d;
PrimalDual<int, int> pd(d + n + m + 2, INF, INF);
int S = d + n + m, T = d + n + m + 1;
REP(i, m) {
int c, s, k; cin >> c >> s >> k; --s;
pd.add_edge(s, d + i, 1, c);
while (k--) {
int a; cin >> a; --a;
pd.add_edge(d + i, d + m + a, 1, 0);
}
}
REP(i, d) {
int b; cin >> b;
// 店 i から買う鍵が b 個以下であれば釣り上げる意味がなくなる
pd.add_edge(S, i, b, 0);
}
REP(i, n) pd.add_edge(d + m + i, T, 1, 0);
int ans = pd.minimum_cost_flow(S, T, n);
cout << (ans == INF ? -1 : ans) << '\n';
return 0;
}
Submission Info
Submission Time |
|
Task |
J - きたまさの逆襲 |
User |
emthrm |
Language |
C++14 (GCC 5.4.1) |
Score |
300 |
Code Size |
5307 Byte |
Status |
AC |
Exec Time |
28 ms |
Memory |
768 KB |
Judge Result
Set Name |
Set 01 |
Set 02 |
Score / Max Score |
50 / 50 |
250 / 250 |
Status |
|
|
Set Name |
Test Cases |
Set 01 |
00_smallest.txt, 01_small_0.txt, 01_small_1.txt, 01_small_10.txt, 01_small_11.txt, 01_small_12.txt, 01_small_13.txt, 01_small_14.txt, 01_small_15.txt, 01_small_16.txt, 01_small_17.txt, 01_small_18.txt, 01_small_19.txt, 01_small_2.txt, 01_small_3.txt, 01_small_4.txt, 01_small_5.txt, 01_small_6.txt, 01_small_7.txt, 01_small_8.txt, 01_small_9.txt, 02_large_0.txt, 02_large_1.txt, 02_large_2.txt, 02_large_3.txt, 02_large_4.txt, 02_large_5.txt, 02_large_6.txt, 02_large_7.txt, 02_large_8.txt, 02_large_9.txt, 09_largest_0.txt, 09_largest_1.txt, 09_largest_2.txt, 09_largest_3.txt, 09_largest_4.txt |
Set 02 |
00_smallest.txt, 01_small_0.txt, 01_small_1.txt, 01_small_10.txt, 01_small_11.txt, 01_small_12.txt, 01_small_13.txt, 01_small_14.txt, 01_small_15.txt, 01_small_16.txt, 01_small_17.txt, 01_small_18.txt, 01_small_19.txt, 01_small_2.txt, 01_small_3.txt, 01_small_4.txt, 01_small_5.txt, 01_small_6.txt, 01_small_7.txt, 01_small_8.txt, 01_small_9.txt, 02_large_0.txt, 02_large_1.txt, 02_large_2.txt, 02_large_3.txt, 02_large_4.txt, 02_large_5.txt, 02_large_6.txt, 02_large_7.txt, 02_large_8.txt, 02_large_9.txt, 09_largest_0.txt, 09_largest_1.txt, 09_largest_2.txt, 09_largest_3.txt, 09_largest_4.txt, 10_smallest.txt, 11_small_0.txt, 11_small_1.txt, 11_small_10.txt, 11_small_11.txt, 11_small_12.txt, 11_small_13.txt, 11_small_14.txt, 11_small_15.txt, 11_small_16.txt, 11_small_17.txt, 11_small_18.txt, 11_small_19.txt, 11_small_2.txt, 11_small_20.txt, 11_small_21.txt, 11_small_22.txt, 11_small_23.txt, 11_small_24.txt, 11_small_25.txt, 11_small_26.txt, 11_small_27.txt, 11_small_28.txt, 11_small_29.txt, 11_small_3.txt, 11_small_4.txt, 11_small_5.txt, 11_small_6.txt, 11_small_7.txt, 11_small_8.txt, 11_small_9.txt, 12_large_0.txt, 12_large_1.txt, 12_large_10.txt, 12_large_11.txt, 12_large_12.txt, 12_large_13.txt, 12_large_14.txt, 12_large_15.txt, 12_large_16.txt, 12_large_17.txt, 12_large_18.txt, 12_large_19.txt, 12_large_2.txt, 12_large_3.txt, 12_large_4.txt, 12_large_5.txt, 12_large_6.txt, 12_large_7.txt, 12_large_8.txt, 12_large_9.txt, 19_largest_0.txt, 19_largest_1.txt, 19_largest_2.txt, 19_largest_3.txt, 19_largest_4.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
00_smallest.txt |
AC |
1 ms |
256 KB |
01_small_0.txt |
AC |
1 ms |
256 KB |
01_small_1.txt |
AC |
1 ms |
256 KB |
01_small_10.txt |
AC |
1 ms |
256 KB |
01_small_11.txt |
AC |
1 ms |
256 KB |
01_small_12.txt |
AC |
1 ms |
256 KB |
01_small_13.txt |
AC |
1 ms |
256 KB |
01_small_14.txt |
AC |
1 ms |
256 KB |
01_small_15.txt |
AC |
1 ms |
256 KB |
01_small_16.txt |
AC |
1 ms |
256 KB |
01_small_17.txt |
AC |
1 ms |
256 KB |
01_small_18.txt |
AC |
1 ms |
256 KB |
01_small_19.txt |
AC |
1 ms |
256 KB |
01_small_2.txt |
AC |
1 ms |
256 KB |
01_small_3.txt |
AC |
1 ms |
256 KB |
01_small_4.txt |
AC |
1 ms |
256 KB |
01_small_5.txt |
AC |
1 ms |
256 KB |
01_small_6.txt |
AC |
1 ms |
256 KB |
01_small_7.txt |
AC |
1 ms |
256 KB |
01_small_8.txt |
AC |
1 ms |
256 KB |
01_small_9.txt |
AC |
1 ms |
256 KB |
02_large_0.txt |
AC |
7 ms |
512 KB |
02_large_1.txt |
AC |
4 ms |
384 KB |
02_large_2.txt |
AC |
13 ms |
512 KB |
02_large_3.txt |
AC |
5 ms |
512 KB |
02_large_4.txt |
AC |
7 ms |
512 KB |
02_large_5.txt |
AC |
16 ms |
512 KB |
02_large_6.txt |
AC |
15 ms |
512 KB |
02_large_7.txt |
AC |
5 ms |
512 KB |
02_large_8.txt |
AC |
4 ms |
384 KB |
02_large_9.txt |
AC |
3 ms |
512 KB |
09_largest_0.txt |
AC |
20 ms |
640 KB |
09_largest_1.txt |
AC |
20 ms |
640 KB |
09_largest_2.txt |
AC |
20 ms |
640 KB |
09_largest_3.txt |
AC |
20 ms |
640 KB |
09_largest_4.txt |
AC |
17 ms |
640 KB |
10_smallest.txt |
AC |
1 ms |
256 KB |
11_small_0.txt |
AC |
1 ms |
256 KB |
11_small_1.txt |
AC |
1 ms |
256 KB |
11_small_10.txt |
AC |
1 ms |
256 KB |
11_small_11.txt |
AC |
1 ms |
256 KB |
11_small_12.txt |
AC |
1 ms |
256 KB |
11_small_13.txt |
AC |
1 ms |
256 KB |
11_small_14.txt |
AC |
1 ms |
256 KB |
11_small_15.txt |
AC |
1 ms |
256 KB |
11_small_16.txt |
AC |
1 ms |
256 KB |
11_small_17.txt |
AC |
1 ms |
256 KB |
11_small_18.txt |
AC |
1 ms |
256 KB |
11_small_19.txt |
AC |
1 ms |
256 KB |
11_small_2.txt |
AC |
1 ms |
256 KB |
11_small_20.txt |
AC |
1 ms |
256 KB |
11_small_21.txt |
AC |
1 ms |
256 KB |
11_small_22.txt |
AC |
1 ms |
256 KB |
11_small_23.txt |
AC |
1 ms |
256 KB |
11_small_24.txt |
AC |
1 ms |
256 KB |
11_small_25.txt |
AC |
1 ms |
256 KB |
11_small_26.txt |
AC |
1 ms |
256 KB |
11_small_27.txt |
AC |
1 ms |
256 KB |
11_small_28.txt |
AC |
1 ms |
256 KB |
11_small_29.txt |
AC |
1 ms |
256 KB |
11_small_3.txt |
AC |
1 ms |
256 KB |
11_small_4.txt |
AC |
1 ms |
256 KB |
11_small_5.txt |
AC |
1 ms |
256 KB |
11_small_6.txt |
AC |
1 ms |
256 KB |
11_small_7.txt |
AC |
1 ms |
256 KB |
11_small_8.txt |
AC |
1 ms |
256 KB |
11_small_9.txt |
AC |
1 ms |
256 KB |
12_large_0.txt |
AC |
9 ms |
452 KB |
12_large_1.txt |
AC |
2 ms |
384 KB |
12_large_10.txt |
AC |
3 ms |
512 KB |
12_large_11.txt |
AC |
14 ms |
512 KB |
12_large_12.txt |
AC |
15 ms |
512 KB |
12_large_13.txt |
AC |
6 ms |
384 KB |
12_large_14.txt |
AC |
9 ms |
384 KB |
12_large_15.txt |
AC |
15 ms |
640 KB |
12_large_16.txt |
AC |
3 ms |
512 KB |
12_large_17.txt |
AC |
17 ms |
512 KB |
12_large_18.txt |
AC |
6 ms |
512 KB |
12_large_19.txt |
AC |
10 ms |
512 KB |
12_large_2.txt |
AC |
8 ms |
512 KB |
12_large_3.txt |
AC |
13 ms |
640 KB |
12_large_4.txt |
AC |
10 ms |
512 KB |
12_large_5.txt |
AC |
2 ms |
384 KB |
12_large_6.txt |
AC |
5 ms |
512 KB |
12_large_7.txt |
AC |
7 ms |
512 KB |
12_large_8.txt |
AC |
4 ms |
384 KB |
12_large_9.txt |
AC |
7 ms |
384 KB |
19_largest_0.txt |
AC |
28 ms |
768 KB |
19_largest_1.txt |
AC |
22 ms |
640 KB |
19_largest_2.txt |
AC |
22 ms |
640 KB |
19_largest_3.txt |
AC |
22 ms |
640 KB |
19_largest_4.txt |
AC |
22 ms |
640 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |