Task: | Download Speed |
Sender: | louaha1 |
Submission time: | 2024-10-24 09:37:36 +0300 |
Language: | C++ (C++11) |
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 | WRONG ANSWER | 0.00 s | details |
#5 | WRONG ANSWER | 0.01 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.01 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | WRONG ANSWER | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | WRONG ANSWER | 0.01 s | details |
#12 | ACCEPTED | 0.00 s | details |
Code
#include <iostream>#include <vector>#include <queue>#include <climits>#include <cstring>using namespace std;const int MAXN = 505; // Maximum number of nodesint capacity[MAXN][MAXN]; // Capacity matrixvector<int> adj[MAXN]; // Adjacency list// Perform BFS to find an augmenting path, and record the path in 'parent'int bfs(int s, int t, vector<int>& parent) {fill(parent.begin(), parent.end(), -1);parent[s] = s;queue<pair<int, int>> q;q.push({s, INT_MAX});while (!q.empty()) {int u = q.front().first;int flow = q.front().second;q.pop();// Traverse all neighbors of ufor (int v : adj[u]) {// If the node is not yet visited and the capacity is greater than 0if (parent[v] == -1 && capacity[u][v] > 0) {parent[v] = u;int new_flow = min(flow, capacity[u][v]);// If we reached the sink, return the flowif (v == t)return new_flow;q.push({v, new_flow});}}}return 0; // No path found}// Edmonds-Karp algorithm to compute the maximum flowint edmonds_karp(int s, int t, int n) {int flow = 0;vector<int> parent(n + 1);while (int new_flow = bfs(s, t, parent)) {flow += new_flow;// Update the capacities of the edges in the augmenting pathint cur = t;while (cur != s) {int prev = parent[cur];capacity[prev][cur] -= new_flow;capacity[cur][prev] += new_flow;cur = prev;}}return flow;}int main() {int n, m;cin >> n >> m;// Initialize the capacity matrix and adjacency listmemset(capacity, 0, sizeof(capacity));// Read the edges and build the graphfor (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;capacity[a][b] += c;capacity[b][a] += c; // Since the graph is undirected, both directions have the same capacityadj[a].push_back(b);adj[b].push_back(a);}// Run the Edmonds-Karp algorithm to find the maximum flow from node 1 to node nint result = edmonds_karp(1, n, n);cout << result << 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: WRONG ANSWER
input |
---|
2 1 2 1 100 |
correct output |
---|
0 |
user output |
---|
100 |
Test 5
Verdict: WRONG ANSWER
input |
---|
2 1000 1 2 1000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 ... |
correct output |
---|
1000000000000 |
user output |
---|
0 |
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: WRONG ANSWER
input |
---|
4 5 1 2 3 2 4 2 1 3 4 3 4 5 ... |
correct output |
---|
6 |
user output |
---|
9 |
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: WRONG ANSWER
input |
---|
10 999 1 2 1000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 ... |
correct output |
---|
111000000000 |
user output |
---|
0 |
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 |