Task: | Airport |
Sender: | aalto2024h_005 |
Submission time: | 2024-10-23 17:25:26 +0300 |
Language: | C++ (C++11) |
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.01 s | details |
#9 | ACCEPTED | 0.01 s | details |
#10 | ACCEPTED | 0.01 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
Code
#include <iostream>#include <limits.h>#include <queue>#include <string.h>#include <vector>using namespace std;bool bfs(vector<vector<long long>>& rGraph, int s, int t, vector<long long>& parent){int V = rGraph.size();vector<bool> visited(V,false);queue<int> q;q.push(s);visited[s] = true;parent[s] = -1;while (!q.empty()) {int u = q.front();q.pop();for (int v = 0; v < V; v++) {if (visited[v] == false && rGraph[u][v] > 0) {if (v == t) {parent[v] = u;return true;}q.push(v);parent[v] = u;visited[v] = true;}}}return false;}long long fordFulkerson(vector<vector<long long>> graph, int s, int t){int u, v;int V = graph.size();vector<vector<long long>> rGraph(V,vector<long long>(V));for (u = 0; u < V; u++)for (v = 0; v < V; v++)rGraph[u][v] = graph[u][v];vector<long long> parent(V);long long max_flow = 0;while (bfs(rGraph, s, t, parent)) {long long path_flow = LONG_LONG_MAX;for (v = t; v != s; v = parent[v]) {u = parent[v];path_flow = min(path_flow, rGraph[u][v]);}for (v = t; v != s; v = parent[v]) {u = parent[v];rGraph[u][v] -= path_flow;rGraph[v][u] += path_flow;}max_flow += path_flow;}return max_flow;}int main(){int n,m;cin >> n >> m;vector<vector<long long>> graph(2*n,vector<long long>(2*n,0));for(int i=0; i< n; i++){long long a;cin >> a;if(a==-1) graph[i][i+n]=LONG_LONG_MAX;else graph[i][(i+n)]=a;}for(int i=0; i<m; i++){int a,b;cin >> a >> b;graph[a-1+n][b-1]=LONG_LONG_MAX;}// for(int i=0; i< 2*n; i++){// for(int l=0; l<2*n; l++){// cout << graph[i][l] << " ";// }// cout << endl;// }cout << fordFulkerson(graph, 0, (2*n)-1) << endl;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
10 20 -1 85 7 19 90 72 11 46 65 -1 6 7 9 7 8 4 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 2
Verdict: ACCEPTED
input |
---|
10 20 -1 80 77 57 77 95 63 98 30 -1 6 7 8 9 7 8 ... |
correct output |
---|
30 |
user output |
---|
30 |
Test 3
Verdict: ACCEPTED
input |
---|
10 20 -1 63 16 42 62 70 9 94 68 -1 10 9 6 8 10 6 ... |
correct output |
---|
25 |
user output |
---|
25 |
Test 4
Verdict: ACCEPTED
input |
---|
10 20 -1 3 86 -1 32 34 9 50 -1 -1 6 7 7 8 9 2 ... |
correct output |
---|
3 |
user output |
---|
3 |
Test 5
Verdict: ACCEPTED
input |
---|
10 20 -1 43 38 -1 7 54 26 97 76 -1 3 9 9 10 6 7 ... |
correct output |
---|
76 |
user output |
---|
76 |
Test 6
Verdict: ACCEPTED
input |
---|
100 1000 -1 425576195 274150382 1021768... |
correct output |
---|
6091126630 |
user output |
---|
6091126630 |
Test 7
Verdict: ACCEPTED
input |
---|
100 1000 -1 769953265 -1 389517741 2323... |
correct output |
---|
769953265 |
user output |
---|
769953265 |
Test 8
Verdict: ACCEPTED
input |
---|
100 1000 -1 584988267 763129662 6781413... |
correct output |
---|
1699511766 |
user output |
---|
1699511766 |
Test 9
Verdict: ACCEPTED
input |
---|
100 1000 -1 921671366 121044688 2933366... |
correct output |
---|
1805833567 |
user output |
---|
1805833567 |
Test 10
Verdict: ACCEPTED
input |
---|
100 1000 -1 763842763 612011030 4532521... |
correct output |
---|
3342235784 |
user output |
---|
3342235784 |
Test 11
Verdict: ACCEPTED
input |
---|
3 3
-1 1 -1 1 2 2 3 2 2 |
correct output |
---|
1 |
user output |
---|
1 |
Test 12
Verdict: ACCEPTED
input |
---|
3 4
-1 1 -1 1 2 1 2 2 3 ... |
correct output |
---|
1 |
user output |
---|
1 |
Test 13
Verdict: ACCEPTED
input |
---|
7 8 -1 1 1 1 1 1 -1 1 2 1 3 2 4 ... |
correct output |
---|
1 |
user output |
---|
1 |