Task: | Download Speed |
Sender: | laluj |
Submission time: | 2024-10-22 23:00:24 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.01 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.01 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.01 s | details |
#12 | WRONG ANSWER | 0.00 s | details |
Code
#include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << ": " << x << endl; #define ll long long #define ull unsigned long long #define vi vector<int> #include <iostream> #include <vector> #include <queue> #include <cstring> #include <algorithm> using namespace std; struct Edge { int to; ull capacity; ull flow; int rev; }; class MaxFlow { public: MaxFlow(int n) : n(n) { adj.resize(n); } void add_edge(int u, int v, ull capacity) { Edge a = {v, capacity, 0, (int)adj[v].size()}; Edge b = {u, 0 , 0, (int)adj[u].size()}; adj[u].push_back(a); adj[v].push_back(b); } ull max_flow(int s, int t) { ull total_flow = 0; while (true) { vector<int> parent(n, -1); vector<int> edge_index(n, -1); queue<int> q; q.push(s); parent[s] = s; while (!q.empty() && parent[t] == -1) { int u = q.front(); q.pop(); for (int i = 0; i < (int) adj[u].size(); i++) { Edge &e = adj[u][i]; if (parent[e.to] == -1 && e.capacity > e.flow) { parent[e.to] = u; edge_index[e.to] = i; q.push(e.to); } } } if (parent[t] == -1) break; ull aug_flow = ULLONG_MAX; for (int v = t; v != s; v = parent[v]) { int u = parent[v]; int idx = edge_index[v]; aug_flow = min(aug_flow, adj[u][idx].capacity - adj[u][idx].flow); } for (int v = t; v != s; v = parent[v]) { int u = parent[v]; int idx = edge_index[v]; adj[u][idx].flow += aug_flow; adj[v][adj[u][idx].rev].flow -= aug_flow; } total_flow += aug_flow; } return total_flow; } private: int n; vector<vector<Edge>> adj; }; int main() { int n, m; cin >> n >> m; MaxFlow maxFlow(n); int a, b; ull c; for (int i = 0; i < m; i++) { cin >> a >> b >> c; a--; b--; maxFlow.add_edge(a, b, c); } cout << maxFlow.max_flow(0, n-1) << endl; return 0; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
4 3 1 2 5 2 3 3 3 4 6 |
correct output |
---|
3 |
user output |
---|
3 |
Test 2
Verdict: ACCEPTED
input |
---|
4 5 1 2 1 1 3 1 2 3 1 2 4 1 ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 3
Verdict: ACCEPTED
input |
---|
4 5 1 2 1000000000 1 3 1000000000 2 3 1 2 4 1000000000 ... |
correct output |
---|
2000000000 |
user output |
---|
2000000000 |
Test 4
Verdict: ACCEPTED
input |
---|
2 1 2 1 100 |
correct output |
---|
0 |
user output |
---|
0 |
Test 5
Verdict: ACCEPTED
input |
---|
2 1000 1 2 1000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 ... |
correct output |
---|
1000000000000 |
user output |
---|
1000000000000 |
Test 6
Verdict: ACCEPTED
input |
---|
500 998 1 2 54 1 3 59 1 4 83 2 5 79 ... |
correct output |
---|
60 |
user output |
---|
60 |
Test 7
Verdict: ACCEPTED
input |
---|
500 998 1 2 530873053 1 3 156306296 1 4 478040476 3 5 303609600 ... |
correct output |
---|
1093765123 |
user output |
---|
1093765123 |
Test 8
Verdict: ACCEPTED
input |
---|
2 1 1 2 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 9
Verdict: ACCEPTED
input |
---|
4 5 1 2 3 2 4 2 1 3 4 3 4 5 ... |
correct output |
---|
6 |
user output |
---|
6 |
Test 10
Verdict: ACCEPTED
input |
---|
4 5 1 2 1 1 3 2 3 2 1 2 4 2 ... |
correct output |
---|
3 |
user output |
---|
3 |
Test 11
Verdict: ACCEPTED
input |
---|
10 999 1 2 1000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 ... |
correct output |
---|
111000000000 |
user output |
---|
111000000000 |
Test 12
Verdict: WRONG ANSWER
input |
---|
7 9 1 2 1 1 3 1 1 4 1 2 5 1 ... |
correct output |
---|
2 |
user output |
---|
1 |