結果
問題 |
No.654 Air E869120
|
ユーザー |
|
提出日時 | 2025-05-16 22:26:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,110 bytes |
コンパイル時間 | 1,762 ms |
コンパイル使用メモリ | 194,860 KB |
実行使用メモリ | 8,604 KB |
最終ジャッジ日時 | 2025-05-16 22:26:34 |
合計ジャッジ時間 | 3,476 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 WA * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 10010, M = 4000010, INF = 2e9; int n, m, k, S, T; struct Edge { int u, v, p, q, w; }edges[N]; int h[N], e[M], ne[M], idx; ll d[N], cur[N], q[N], f[M]; void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++ ; e[idx] = a, ne[idx] = h[b], h[b] = idx ++ ; } bool bfs() { int hh = 0, tt = 0; memset(d, -1, sizeof d); q[0] = S, d[S] = 0, cur[S] = h[S]; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (d[j] == -1 && f[i]) { d[j] = d[t] + 1; cur[j] = h[j]; if (j == T) return true; q[ ++ tt] = j; } } } return false; } int find(int u, int limit) { if (u == T) return limit; ll flow = 0; for (int i = h[u]; ~i; i = ne[i]) { cur[u] = i; int j = e[i]; if (d[j] == d[u] + 1 && f[i]) { int t = find(j, min(f[i], limit - flow)); if (!t) d[j] = -1; f[i] -= t, f[i ^ 1] += t, flow += t; } } return flow; } ll dinic() { ll r = 0, flow = 0; while (bfs()) while (flow = find(S, INF)) r += flow; return r; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(h, -1, sizeof h); cin >> n >> m >> k; for (int i = 1; i <= m; i ++ ) cin >> edges[i].u >> edges[i].v >> edges[i].p >> edges[i].q >> edges[i].w; for (int i = 1; i <= m; i ++ ) add(i + m, edges[i].u, edges[i].w), add(i + m, edges[i].v, edges[i].w); for (int i = 1; i <= m; i ++ ) for (int j = 1; j <= m; j ++ ) if (i != j) { if (edges[i].v != edges[j].u) continue; if (edges[i].q + k > edges[j].p) continue; add(i + m, j + m, INF); } S = 2 * m + 1, T = 2 * m + 2; for (int i = 1; i <= m; i ++ ) { if (edges[i].u == 1) add(S, i + m, edges[i].w); if (edges[i].v == n) add(i + m, T, edges[i].w); } cout << dinic() << "\n"; return 0; }