Task: | Download Speed |
Sender: | laluj |
Submission time: | 2024-10-22 23:10:43 +0300 |
Language: | C++ (C++17) |
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.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.00 s | details |
#12 | ACCEPTED | 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;// }#include <iostream>#include <vector>#include <queue>#include <algorithm>#include <limits>using namespace std;#define ull unsigned long longclass 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 vvoid 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 pathvector<int> parent(n, -1); // To store the path (parent of each node)queue<pair<int, ull>> q; // Queue for BFSq.push({s, ULLONG_MAX});parent[s] = s; // Mark source as visited by assigning itself as parentwhile (!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 visitedif (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 pathtotal_flow += new_flow;int cur = v;while (cur != s) {int prev = parent[cur];capacity[prev][cur] -= new_flow; // Reduce capacity along pathcapacity[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 doneif (parent[t] == -1)break;next_iteration:;}return total_flow;}private:int n; // Number of nodesvector<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 ca--; b--; // 1-based to 0-based indexingmaxFlow.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 |