CSES - Aalto Competitive Programming 2024 - wk7 Homework - Results
Submission details
Task:Download Speed
Sender:laluj
Submission time:2024-10-22 23:10:43 +0300
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails

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;
// }
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;
#define ull unsigned long long
class MaxFlow {
public:
MaxFlow(int n) : n(n) {
capacity.assign(n, vector<ull>(n, 0)); // Initialize capacity matrix with 0
}
// Add edge with capacity between nodes u and v
void add_edge(int u, int v, ull cap) {
capacity[u][v] += cap; // Set the capacity of the edge from u to v
}
ull max_flow(int s, int t) {
ull total_flow = 0;
while (true) {
// Perform BFS to find an augmenting path
vector<int> parent(n, -1); // To store the path (parent of each node)
queue<pair<int, ull>> q; // Queue for BFS
q.push({s, ULLONG_MAX});
parent[s] = s; // Mark source as visited by assigning itself as parent
while (!q.empty() && parent[t] == -1) {
int u = q.front().first;
ull flow = q.front().second;
q.pop();
for (int v = 0; v < n; v++) {
// If there's remaining capacity and v is not visited
if (parent[v] == -1 && capacity[u][v] > 0) {
parent[v] = u;
ull new_flow = min(flow, capacity[u][v]);
if (v == t) {
// If we reached the sink, update capacities along the path
total_flow += new_flow;
int cur = v;
while (cur != s) {
int prev = parent[cur];
capacity[prev][cur] -= new_flow; // Reduce capacity along path
capacity[cur][prev] += new_flow; // Add reverse flow (residual)
cur = prev;
}
goto next_iteration; // Break out of the BFS loop and continue
}
q.push({v, new_flow});
}
}
}
// If no augmenting path was found, we're done
if (parent[t] == -1)
break;
next_iteration:;
}
return total_flow;
}
private:
int n; // Number of nodes
vector<vector<ull>> capacity; // Capacity matrix
};
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; // Input edge from a to b with capacity c
a--; b--; // 1-based to 0-based indexing
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: ACCEPTED

input
7 9
1 2 1
1 3 1
1 4 1
2 5 1
...

correct output
2

user output
2