Task: | Internet connection |
Sender: | dsedov |
Submission time: | 2018-09-15 14:49:04 +0300 |
Language: | C++ |
Status: | READY |
Result: | RUNTIME ERROR |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | ACCEPTED | 0.01 s | details |
#3 | ACCEPTED | 0.02 s | details |
#4 | ACCEPTED | 0.01 s | details |
#5 | ACCEPTED | 0.01 s | details |
#6 | RUNTIME ERROR | 0.01 s | details |
#7 | RUNTIME ERROR | 0.02 s | details |
#8 | RUNTIME ERROR | 0.02 s | details |
#9 | RUNTIME ERROR | 0.03 s | details |
#10 | RUNTIME ERROR | 0.02 s | details |
Code
#include <stdio.h> #include <iostream> #include <memory.h> #include <string> #include <algorithm> #include <vector> using namespace std; #define sqr(a) ((a) * (a)) #define pi 3.1415926535897932384626433832795 //#define TASK "b" #define MAXE 1005 #define MAXN 105 const long long cmax = 1e10; int n, m; long long fst[MAXN], was[MAXN], nxt[MAXE], en[MAXE], edge[MAXN][MAXN]; long long c[MAXN][MAXN], f[MAXN][MAXN]; int cnt; int u, t; void AddEdge(int a, int b, int cap) { nxt[cnt] = fst[a]; fst[a] = cnt; en[cnt] = b; edge[a][b] = cnt; c[a][b] = cap; cnt++; nxt[cnt] = fst[b]; fst[b] = cnt; en[cnt] = a; edge[a][b] = cnt; cnt++; } void Load() { memset(fst, -1, sizeof(fst)); cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, cap; cin >> a >> b >> cap; AddEdge(a,b,cap); } } long long dfs(int v, long long cmin) { if (v == t) return cmin; was[v] = 1; for(int i = fst[v]; i != -1; i = nxt[i]) { if(was[en[i]] == -1 && f[v][en[i]] < c[v][en[i]]) { long long delta = dfs(en[i], min(cmin, c[v][en[i]] - f[v][en[i]])); if (delta > 0) { f[v][en[i]] += delta; f[en[i]][v] -= delta; return delta; } } } return 0; } void Solve() { u = 1, t = n; memset(was, -1, sizeof(was)); long long ans = 0; long long flow = dfs(u, cmax); while( flow > 0) { memset(was, -1, sizeof(was)); ans += flow; flow = dfs(u, cmax); } cout << ans; } int main() { //freopen(TASK".in", "r", stdin); //freopen(TASK".out", "w", stdout); Load(); Solve(); return 0; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
10 20 5 6 19 4 5 47 3 5 7 4 9 62 ... |
correct output |
---|
73 |
user output |
---|
73 |
Test 2
Verdict: ACCEPTED
input |
---|
10 20 2 4 63 7 9 54 6 7 16 2 3 9 ... |
correct output |
---|
110 |
user output |
---|
110 |
Test 3
Verdict: ACCEPTED
input |
---|
10 20 5 6 90 2 3 46 7 8 80 6 7 60 ... |
correct output |
---|
29 |
user output |
---|
29 |
Test 4
Verdict: ACCEPTED
input |
---|
10 20 3 4 76 5 7 8 3 8 71 4 7 24 ... |
correct output |
---|
95 |
user output |
---|
95 |
Test 5
Verdict: ACCEPTED
input |
---|
10 20 1 8 22 6 7 40 4 5 20 8 10 77 ... |
correct output |
---|
156 |
user output |
---|
156 |
Test 6
Verdict: RUNTIME ERROR
input |
---|
100 1000 63 85 864540192 22 91 974117435 64 66 953124912 85 88 6080960 ... |
correct output |
---|
4397669179 |
user output |
---|
(empty) |
Test 7
Verdict: RUNTIME ERROR
input |
---|
100 1000 36 93 760720873 12 75 175717522 78 79 340128710 80 83 181753465 ... |
correct output |
---|
5298558023 |
user output |
---|
(empty) |
Test 8
Verdict: RUNTIME ERROR
input |
---|
100 1000 20 60 909693891 55 91 570199535 21 41 118646902 37 82 824735480 ... |
correct output |
---|
5466229311 |
user output |
---|
(empty) |
Test 9
Verdict: RUNTIME ERROR
input |
---|
100 1000 26 44 753330451 62 67 821574279 70 95 219303983 7 44 980013084 ... |
correct output |
---|
4893925638 |
user output |
---|
(empty) |
Test 10
Verdict: RUNTIME ERROR
input |
---|
100 1000 15 89 501388091 50 71 396801720 15 92 324349822 29 85 184420157 ... |
correct output |
---|
6956499595 |
user output |
---|
(empty) |