| 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) |
