Task: | Download Speed |
Sender: | odanobunaga8199 |
Submission time: | 2024-10-21 18:53:50 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
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.00 s | details |
#6 | ACCEPTED | 0.00 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.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
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 networkstruct Edge {int to; // Destination nodeint 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 Algorithmclass MaxFlow {public:int N; // Number of nodesvector<vector<Edge>> graph; // Adjacency listvector<int> level; // Level of each node for BFSvector<int> ptr; // Current edge to explore for each node in DFS// Constructor to initialize the graphMaxFlow(int N) : N(N), graph(N + 1), level(N + 1, -1), ptr(N + 1, 0) {}// Function to add an edge to the graphvoid 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 levelsbool 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 pathslong 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 tlong 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 graphfor(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 nlong 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 |