Submission details
Task:Internet connection
Sender:phid
Submission time:2020-09-19 15:15:12 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#60.01 sdetails
#70.01 sdetails
#80.01 sdetails
#90.01 sdetails
#100.01 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.01 sdetails
#130.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.01 sdetails
#180.01 sdetails
#190.01 sdetails
#200.01 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.01 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:64:23: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'long int' [-Wformat=]
     printf("%lld", ans);
                       ^

Code

#include <bits/stdc++.h>

using namespace std;

int n, m, s, t;
int inf = 999999999;
vector<int> a[100];
int c[100][100];
int f[100][100];
int d[100];

bool bfs(int s, int t) {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        d[i] = 0;
    d[s] = inf;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == t)
            return true;
        for (int v : a[u])
            if (d[v] == 0 && c[u][v] > f[u][v]) {
                d[v] = u;
                q.push(v);
            }
    }
    return false;
}

void maxflow() {
    int u, v, diff = inf;
    for (v = t; v != s; v = d[v]) {
        u = d[v];
        if (diff > c[u][v] - f[u][v])
            diff = c[u][v] - f[u][v];
    }
    for (v = t; v != s; v = u) {
        u = d[v];
        f[u][v] += diff;
        f[v][u] -= diff;
    }
}

int main() {
    cin >> n >> m;
    s = 1;
    t = n;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back(v);
        a[v].push_back(u);
        c[u][v] = w;
    }
    while (bfs(s, t))
        maxflow();

    long ans = 0;
    for (int v : a[s])
        ans += f[s][v];
    printf("%lld", ans);
    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:

input
100 1000
63 85 864540192
22 91 974117435
64 66 953124912
85 88 6080960
...

correct output
4397669179

user output
(empty)

Test 7

Verdict:

input
100 1000
36 93 760720873
12 75 175717522
78 79 340128710
80 83 181753465
...

correct output
5298558023

user output
(empty)

Test 8

Verdict:

input
100 1000
20 60 909693891
55 91 570199535
21 41 118646902
37 82 824735480
...

correct output
5466229311

user output
(empty)

Test 9

Verdict:

input
100 1000
26 44 753330451
62 67 821574279
70 95 219303983
7 44 980013084
...

correct output
4893925638

user output
(empty)

Test 10

Verdict:

input
100 1000
15 89 501388091
50 71 396801720
15 92 324349822
29 85 184420157
...

correct output
6956499595

user output
(empty)

Test 11

Verdict: ACCEPTED

input
2 1
1 2 1

correct output
1

user output
1

Test 12

Verdict: ACCEPTED

input
2 1
2 1 1

correct output
0

user output
0

Test 13

Verdict:

input
2 2
1 2 1
2 1 1

correct output
1

user output
2

Test 14

Verdict: ACCEPTED

input
100 1000
1 2 539540023
2 3 244306651
3 4 253259012
3 5 630461598
...

correct output
0

user output
0

Test 15

Verdict: ACCEPTED

input
4 5
1 2 2
1 3 5
2 4 3
3 2 2
...

correct output
4

user output
4

Test 16

Verdict: ACCEPTED

input
2 0

correct output
0

user output
0

Test 17

Verdict: ACCEPTED

input
100 0

correct output
0

user output
0

Test 18

Verdict:

input
100 196
1 2 1000000000
2 100 1000000000
1 3 1000000000
3 100 1000000000
...

correct output
98000000000

user output
(empty)

Test 19

Verdict:

input
100 99
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
...

correct output
1000000000

user output
(empty)

Test 20

Verdict:

input
2 2
2 1 1
1 2 1

correct output
1

user output
2

Test 21

Verdict: ACCEPTED

input
4 6
1 2 1000000000
1 3 1000000000
2 3 1
2 4 1000000000
...

correct output
2000000000

user output
2000000000

Test 22

Verdict: ACCEPTED

input
4 6
1 2 1000000000
1 3 1000000000
2 4 1000000000
2 3 1
...

correct output
2000000000

user output
2000000000