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

Compiler report

input/code.cpp: In member function 'long long int MaxFlow::dfs(int, int, long long int)':
input/code.cpp:51:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int &cid = ptr[v]; cid < graph[v].size(); cid++) {
      |                                ~~~~^~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
// Structure to represent an edge in the flow network
struct Edge {
int to; // Destination node
int rev; // Index of the reverse edge in the adjacency list of 'to'
long long cap; // Capacity of the edge
};
// Class to represent the flow network and perform Dinic's Algorithm
class MaxFlow {
public:
int N; // Number of nodes
vector<vector<Edge>> graph; // Adjacency list
vector<int> level; // Level of each node for BFS
vector<int> ptr; // Current edge to explore for each node in DFS
// Constructor to initialize the graph
MaxFlow(int N) : N(N), graph(N + 1), level(N + 1, -1), ptr(N + 1, 0) {}
// Function to add an edge to the graph
void add_edge(int from, int to, long long cap) {
Edge a = {to, (int)graph[to].size(), cap};
Edge b = {from, (int)(graph[from].size()), 0};
graph[from].push_back(a);
graph[to].push_back(b);
}
// BFS to construct levels
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue<int> q;
q.push(s);
level[s] = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
for(auto &e : graph[v]) {
if(e.cap > 0 && level[e.to] == -1){
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
// DFS to find augmenting paths
long long dfs(int v, int t, long long pushed) {
if(v == t) return pushed;
for(int &cid = ptr[v]; cid < graph[v].size(); cid++) {
Edge &e = graph[v][cid];
if(e.cap > 0 && level[e.to] == level[v] + 1){
long long tr = dfs(e.to, t, min(pushed, e.cap));
if(tr > 0){
e.cap -= tr;
graph[e.to][e.rev].cap += tr;
return tr;
}
}
}
return 0;
}
// Function to compute the maximum flow from s to t
long long max_flow_func(int s, int t){
long long flow = 0;
while(bfs(s, t)){
fill(ptr.begin(), ptr.end(), 0);
while(long long pushed = dfs(s, t, 1e18)){
flow += pushed;
}
}
return flow;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
MaxFlow mf(n);
// Read connections and build the graph
for(int i = 0; i < m; i++){
int a, b;
long long c;
cin >> a >> b >> c;
mf.add_edge(a, b, c);
}
// Compute the maximum flow from node 1 to node n
long long max_flow = mf.max_flow_func(1, n);
cout << max_flow;
}

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