QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#665718#898. 二分图最大匹配Zhou_JKAC ✓118ms12928kbC++231.6kb2024-10-22 14:56:222024-10-22 14:56:23

Judging History

你现在查看的是最新测评结果

  • [2024-10-22 14:56:23]
  • 评测
  • 测评结果:AC
  • 用时:118ms
  • 内存:12928kb
  • [2024-10-22 14:56:22]
  • 提交

answer

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

struct augment_path {
  vector<vector<int>> g;
  vector<int> pa;  // 匹配
  vector<int> pb;
  vector<int> vis;  // 访问
  int n, m;         // 顶点和边的数量
  int dfn;          // 时间戳记
  int res;          // 匹配数

  augment_path(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    vis = vector<int>(n);
    g.resize(n);
    res = 0;
    dfn = 0;
  }

  void add(int from, int to) {
    assert(0 <= from && from < n && 0 <= to && to < m);
    g[from].push_back(to);
  }

  bool dfs(int v) {
    vis[v] = dfn;
    for (int u : g[v]) {
      if (pb[u] == -1) {
        pb[u] = v;
        pa[v] = u;
        return true;
      }
    }
    for (int u : g[v]) {
      if (vis[pb[u]] != dfn && dfs(pb[u])) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    return false;
  }

  int solve() {
    while (true) {
      dfn++;
      int cnt = 0;
      for (int i = 0; i < n; i++) {
        if (pa[i] == -1 && dfs(i)) {
          cnt++;
        }
      }
      if (cnt == 0) {
        break;
      }
      res += cnt;
    }
    return res;
  }
};

int main() {
  int n, m, e;
  cin >> n >> m >> e;
  augment_path solver(n, m);
  int u, v;
  for (int i = 0; i < e; i++) {
    cin >> u >> v;
    solver.add(u, v);
  }
  cout << solver.solve() << "\n";
  for (int i = 0; i < n; i++) {
    if(solver.pa[i] != -1) cout << i << " " << solver.pa[i] << "\n";
  }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 118ms
memory: 12256kb

input:

100000 100000 200000
78474 45795
32144 46392
92549 13903
73460 34144
96460 92850
56318 77066
77529 84436
76342 51542
77506 99268
76410 89381
1778 61392
43607 96135
84268 74827
14857 35966
32084 94908
19876 174
1481 94390
12423 55019
64368 92587
81295 7902
25432 46032
36293 61128
73555 84836
8418 102...

output:

100000
0 54731
1 26066
2 89637
3 1717
4 68505
5 28330
6 55261
7 34703
8 42170
9 23249
10 90437
11 69580
12 72086
13 47593
14 29944
15 87183
16 763
17 2814
18 46044
19 75228
20 11487
21 72701
22 60611
23 36775
24 66081
25 45592
26 3321
27 88211
28 71467
29 47516
30 55528
31 83162
32 46298
33 26459
34...

result:

ok OK

Test #2:

score: 0
Accepted
time: 110ms
memory: 12928kb

input:

100000 100000 200000
56815 52516
2576 76201
40377 1757
50463 66496
15833 50879
9828 16330
80692 9962
51095 17590
15870 35191
91301 65509
90774 57492
11890 8966
44786 41895
3386 35478
93470 47452
84803 93635
90745 34876
18201 38717
7472 34257
36580 19532
13248 27524
6441 69869
8821 61870
94536 67713
...

output:

100000
0 49451
1 29914
2 31512
3 87445
4 91463
5 83824
6 17634
7 33390
8 66264
9 12388
10 9428
11 77732
12 80853
13 15512
14 39374
15 63409
16 17216
17 7319
18 83326
19 39754
20 25212
21 6189
22 61240
23 26716
24 73214
25 18227
26 17935
27 44486
28 6804
29 36155
30 36983
31 34087
32 39785
33 73657
3...

result:

ok OK

Test #3:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2

output:

3
0 0
1 1
2 2

result:

ok OK

Test #4:

score: 0
Accepted
time: 88ms
memory: 9756kb

input:

100000 100000 199999
25370 25370
85964 85963
415 415
16796 16796
12437 12437
45409 45408
63005 63004
22155 22155
87828 87827
84013 84013
37307 37307
72324 72324
83703 83703
55390 55389
6780 6779
78090 78090
9375 9375
82192 82192
74694 74694
49841 49841
15798 15798
69855 69854
82948 82947
97389 97388...

output:

100000
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
5...

result:

ok OK

Test #5:

score: 0
Accepted
time: 79ms
memory: 9728kb

input:

100000 100000 199999
59469 59469
76773 76772
89516 89516
87040 87040
90184 90184
83075 83075
61454 61454
33615 33615
85794 85793
92072 92071
49725 49725
63842 63841
99247 99247
24121 24121
29552 29551
73533 73533
75845 75845
27029 27028
84418 84418
26636 26636
10100 10099
75013 75012
67341 67341
756...

output:

100000
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
5...

result:

ok OK

Test #6:

score: 0
Accepted
time: 106ms
memory: 10296kb

input:

100000 100000 199999
22284 45795
32144 44930
58734 13903
57136 34144
7548 92850
56318 11874
77529 85278
27039 51542
77506 94257
69265 89381
67073 61392
86159 96135
83227 74827
14857 19500
32084 73639
86884 174
27268 94390
20020 55019
45357 92587
17833 7902
55801 46032
36293 46557
73555 13746
8418 88...

output:

100000
0 2401
1 18084
2 59700
3 99457
4 33291
5 38417
6 97167
7 64564
8 28471
9 68817
10 62095
11 31609
12 57675
13 28348
14 2599
15 99163
16 58923
17 17629
18 3975
19 53920
20 25930
21 4206
22 49364
23 55768
24 40573
25 87244
26 12858
27 39608
28 42953
29 68974
30 89214
31 48329
32 3980
33 50041
34...

result:

ok OK

Test #7:

score: 0
Accepted
time: 103ms
memory: 10164kb

input:

100000 100000 199999
4850 52516
2576 29250
69016 1757
85854 66496
48300 50879
83741 16330
98931 9962
38730 17590
15870 13960
91301 97595
81692 57492
11890 59332
5076 41895
23574 35478
93470 65245
61976 93635
96140 34876
18201 35366
64057 34257
25588 19532
13248 91003
6441 83448
99191 61870
94536 169...

output:

100000
0 39785
1 26716
2 6189
3 33390
4 12388
5 6804
6 66264
7 36155
8 25212
9 73214
10 29914
11 87445
12 9428
13 44486
14 83326
15 61240
16 63409
17 15512
18 77732
19 17216
20 39374
21 7319
22 36983
23 45568
24 34087
25 31512
26 83824
27 73657
28 80853
29 58211
30 14867
31 17935
32 49451
33 91463
3...

result:

ok OK

Test #8:

score: 0
Accepted
time: 83ms
memory: 7380kb

input:

61217 61379 199943
14003 13749
24504 24347
30371 30219
27661 27461
33247 33397
38346 38157
17300 16944
50476 50643
56488 56551
46690 46949
21355 21288
3899 3659
24330 24165
8806 8305
40957 40994
15089 14813
20397 20389
30864 30800
33635 33755
20900 20808
55447 55499
4335 4040
36726 36551
16496 16095...

output:

37154
0 0
11 2
12 10
13 4
14 13
15 8
16 5
17 3
18 12
19 9
20 11
21 1
22 15
23 14
30 20
31 28
32 29
33 35
34 22
35 31
36 46
39 39
41 44
42 38
44 40
45 45
49 51
50 54
51 53
52 52
53 55
64 65
66 57
70 61
71 63
79 73
80 72
81 69
83 71
84 74
85 67
87 77
88 78
89 76
90 75
93 80
101 79
107 85
109 96
111 95...

result:

ok OK

Test #9:

score: 0
Accepted
time: 78ms
memory: 7348kb

input:

61352 60513 199960
2270 2419
38842 39327
48788 48843
2493 2635
40183 40659
59754 59010
48980 48993
52508 52276
12892 13195
33811 34565
40260 40700
2116 2289
11742 12133
29439 29942
4256 4392
51422 51263
44695 44994
21600 22165
21666 22208
26472 26785
49979 50038
12099 12515
10539 10816
32736 33401
3...

output:

37442
0 5
1 9
2 10
3 2
4 7
5 3
7 20
8 22
9 13
10 18
11 26
12 23
13 24
14 27
15 32
17 37
18 35
19 38
20 34
23 36
32 56
33 41
34 51
35 53
36 66
37 72
38 71
39 75
40 74
41 76
42 70
43 73
44 68
48 69
52 80
53 87
54 83
55 81
56 86
57 79
58 82
59 84
60 78
61 88
62 85
63 77
64 94
65 90
66 101
67 92
68 93
6...

result:

ok OK

Test #10:

score: 0
Accepted
time: 88ms
memory: 9464kb

input:

100000 100000 199998
0 13805
0 33641
1 9259
1 62738
1 70691
1 78118
2 41148
3 15765
3 50059
4 96644
5 91521
6 32562
8 2550
8 11396
8 48345
9 14639
9 51057
9 79293
9 92374
10 64733
10 67020
11 7764
11 46822
11 60302
12 8749
12 27869
12 69569
12 71510
13 35684
13 42579
13 82023
14 34778
15 1975
15 693...

output:

78404
0 13805
1 9259
2 41148
3 15765
4 96644
5 91521
6 32562
8 2550
9 51057
10 67020
11 7764
12 69569
13 42579
14 34778
15 69322
16 51422
17 6162
18 9164
19 64579
21 24593
22 94934
23 77417
24 47998
25 24157
27 53506
28 35478
29 65316
30 31954
31 19608
32 71996
34 64699
35 72885
36 89653
37 57779
38...

result:

ok OK

Test #11:

score: 0
Accepted
time: 91ms
memory: 9464kb

input:

100000 100000 199998
0 28389
0 41333
0 66666
1 5984
1 15912
3 63753
3 77735
4 25015
4 30450
4 90212
5 66978
5 98909
6 63465
6 78227
6 78950
6 85422
7 1743
7 1868
7 55171
8 37582
9 26491
9 82984
10 29229
10 29811
10 33063
11 10609
11 48601
11 73298
11 95658
12 29064
12 50261
12 63186
12 68616
13 8683...

output:

78497
0 41333
1 5984
3 63753
4 30450
5 98909
6 85422
7 1868
8 37582
9 26491
10 29229
11 95658
12 50261
13 86837
14 61234
15 77990
16 10803
17 23926
18 93717
19 32559
21 15495
23 47490
24 34533
25 23940
26 36458
27 33773
28 89481
29 83766
30 28313
31 82347
32 28749
33 69818
34 35265
35 82877
36 24476...

result:

ok OK

Test #12:

score: 0
Accepted
time: 88ms
memory: 9468kb

input:

100000 100000 199997
0 4357
0 35525
0 51857
1 57468
1 94927
1 96004
3 75468
4 20202
4 37102
5 32207
6 8677
6 16775
6 46813
6 75640
7 30806
8 4099
8 26454
8 49376
8 55539
8 67032
9 82362
10 11387
10 33778
10 35352
10 50533
10 54706
11 44868
11 59104
14 80528
14 90600
14 99752
15 10954
15 80519
15 873...

output:

78379
0 4357
1 57468
3 75468
4 37102
5 32207
6 75640
7 30806
8 26454
9 82362
10 54706
11 59104
14 80528
15 10954
16 32575
17 88162
18 52112
19 49350
20 58977
21 31926
22 50244
23 5726
24 92464
26 50093
27 57836
28 96888
30 50525
31 76950
32 73647
33 971
34 36879
35 81872
36 660
37 65791
38 55672
39 ...

result:

ok OK

Test #13:

score: 0
Accepted
time: 3ms
memory: 4156kb

input:

17707 77101 11866
4 29611
4 62770
4 65605
5 22177
5 57724
14 59632
14 68649
17 9622
18 9221
18 43355
29 19612
30 44428
32 51277
34 53196
35 20939
37 68142
38 34663
38 36432
39 71932
40 62217
41 40291
43 53542
44 22018
44 60539
47 56819
47 76081
49 18326
50 52876
50 58006
51 64709
51 66011
52 26751
5...

output:

8453
4 29611
5 22177
14 59632
17 9622
18 9221
29 19612
30 44428
32 51277
34 53196
35 20939
37 68142
38 34663
39 71932
40 62217
41 40291
43 53542
44 22018
47 56819
49 18326
50 52876
51 64709
52 26751
54 5453
55 72966
57 3550
58 64790
59 16851
60 49400
62 16210
67 18050
68 27089
70 47489
71 41622
73 5...

result:

ok OK

Test #14:

score: 0
Accepted
time: 59ms
memory: 7640kb

input:

69830 19691 148749
0 8565
0 12093
0 12608
2 777
2 8771
3 6106
3 7526
3 10596
3 12199
3 14674
3 17676
4 4643
4 15016
4 17194
6 6948
7 1743
7 7750
8 2305
8 4814
9 4468
9 12246
9 16763
9 17448
10 295
10 12043
10 13971
11 168
11 4447
11 7762
11 15833
11 15993
12 1914
12 3080
12 5649
14 29
15 1675
15 464...

output:

19684
0 12093
2 777
3 6106
4 4643
6 6948
7 1743
8 2305
9 4468
10 295
11 168
12 1914
14 29
15 12454
16 10804
17 1653
18 4512
20 5430
21 2932
22 1202
23 5092
24 3698
25 95
26 14930
27 6935
29 18230
30 6797
31 1075
32 1090
33 3177
34 10683
36 1439
37 5898
38 2502
40 6932
41 18160
42 245
43 3422
44 5809...

result:

ok OK

Test #15:

score: 0
Accepted
time: 37ms
memory: 6476kb

input:

53336 61958 92222
0 23730
0 34075
0 35525
1 30468
1 61015
3 24509
3 36308
4 8061
4 45185
4 54435
5 32530
5 59288
6 10104
6 56657
10 2203
10 3106
10 33778
11 29821
11 59104
12 27897
14 18850
15 13472
15 14983
15 37131
15 40140
15 49346
15 59901
16 12876
16 32645
18 26571
21 60370
22 39980
22 41044
22...

output:

40194
0 23730
1 61015
3 24509
4 8061
5 59288
6 10104
10 2203
11 29821
12 27897
14 18850
15 14983
16 12876
18 26571
21 60370
22 39980
23 59945
24 17646
25 7805
26 55641
27 528
28 37215
29 61757
30 51900
32 18385
33 14342
34 19082
35 30280
36 24688
37 59801
39 7675
40 21280
42 10909
43 28881
44 12450
...

result:

ok OK

Test #16:

score: 0
Accepted
time: 59ms
memory: 6148kb

input:

36033 25839 130375
0 1577
0 16725
0 22301
0 24558
1 5977
1 6738
1 9339
1 25294
2 762
2 6992
2 10207
2 14608
3 3
3 3002
3 25047
4 12402
4 13815
4 15862
5 4727
6 6680
6 8345
6 10057
6 13352
6 17084
7 9878
7 17893
7 21628
7 23892
8 2601
8 13004
8 19099
8 23028
9 2307
9 13011
9 15776
9 22642
11 7388
11 ...

output:

25668
0 24558
1 5977
2 10207
3 3
4 15862
5 4727
6 10057
7 9878
8 19099
9 15776
11 15341
13 23460
14 2916
15 22521
17 14549
18 918
19 9493
20 7972
21 16661
22 4518
23 10636
24 19602
25 10609
26 1468
27 22575
28 5879
29 9367
30 16096
31 20612
32 19736
33 11274
34 25554
35 16587
37 1830
38 3460
39 5015...

result:

ok OK

Test #17:

score: 0
Accepted
time: 11ms
memory: 4448kb

input:

14868 99117 25214
0 19546
0 37951
1 13804
1 18263
1 38541
1 49319
1 64693
1 81665
1 91777
2 2159
2 8896
4 38134
5 3464
5 52631
6 85971
6 92674
7 5530
7 12991
7 35465
8 12077
8 71946
9 57520
11 75486
11 95227
12 83001
13 83429
13 85532
15 32388
15 49234
15 87159
16 70733
16 95797
17 45027
18 51284
20...

output:

12003
0 19546
1 13804
2 2159
4 38134
5 3464
6 85971
7 5530
8 12077
9 57520
11 75486
12 83001
13 83429
15 32388
16 70733
17 45027
18 51284
20 38605
21 5520
23 86112
26 29339
27 7626
28 24622
30 6132
33 30727
34 2843
37 81810
38 72113
39 11712
40 81311
41 37091
43 49309
44 83232
46 7245
47 92399
48 70...

result:

ok OK

Test #18:

score: 0
Accepted
time: 20ms
memory: 6056kb

input:

53098 9437 57924
0 262
0 3336
0 7251
2 2976
3 4877
4 3403
4 8279
5 4742
6 2961
6 8901
8 5979
8 8808
9 7822
10 415
12 969
13 1058
15 3592
17 5759
18 7128
19 4461
19 9343
20 5011
20 8942
21 8414
22 5217
22 5266
22 5455
23 5698
23 8697
24 5855
25 1211
25 2830
28 3685
29 1866
29 8645
32 6955
32 7045
33 ...

output:

9415
0 262
2 2976
3 4877
4 3403
5 4742
6 2961
8 5979
9 7822
10 415
12 969
13 1058
15 3592
17 5759
18 7128
19 4461
20 5011
21 8414
22 5217
23 5698
24 5855
25 1211
28 3685
29 1866
32 6955
33 2484
34 7733
36 302
37 7754
40 5766
43 5144
44 1709
45 2552
46 6881
47 901
49 1104
50 7235
51 760
52 4351
55 42...

result:

ok OK

Test #19:

score: 0
Accepted
time: 77ms
memory: 7324kb

input:

62342 62612 153201
0 1819
1 26257
1 34654
1 41966
2 9609
3 19007
3 31306
3 36054
4 36681
4 42043
4 46885
4 54123
5 35272
5 48535
6 9177
6 44477
7 11189
7 17566
7 41426
7 53724
8 13815
8 36015
8 48166
10 1144
10 2928
10 21148
10 21677
10 46645
12 39907
12 53275
13 52579
14 21089
15 39807
16 46513
17 ...

output:

53671
0 1819
1 41966
2 9609
3 31306
4 36681
5 48535
6 9177
7 41426
8 48166
10 1144
12 53275
13 52579
14 21089
15 39807
16 46513
17 57314
18 48300
19 49799
20 58031
21 6661
22 30788
24 43728
27 53143
28 60322
29 45277
30 49076
31 16727
32 22621
33 23347
34 12047
36 9660
37 13583
38 10615
39 44936
40 ...

result:

ok OK

Test #20:

score: 0
Accepted
time: 11ms
memory: 6984kb

input:

95835 11475 31126
7 7489
10 1813
17 1852
18 9253
21 2999
25 1649
28 7088
33 4068
33 6119
34 5651
39 10350
41 5703
43 7512
51 3934
52 4246
55 4275
55 6549
64 8185
66 10080
67 10332
73 6343
73 6432
80 8844
86 1764
87 5646
92 399
95 509
95 9564
102 10598
107 582
121 5613
122 5866
123 7063
125 4180
125 ...

output:

10716
7 7489
10 1813
17 1852
18 9253
21 2999
25 1649
28 7088
33 4068
34 5651
39 10350
41 5703
43 7512
51 3934
52 4246
55 4275
64 8185
66 10080
67 10332
73 6343
80 8844
86 1764
87 5646
92 399
95 509
102 10598
107 582
121 5613
122 5866
123 7063
125 4180
126 4185
137 7604
138 2255
140 9700
141 7624
144...

result:

ok OK

Test #21:

score: 0
Accepted
time: 58ms
memory: 4704kb

input:

5824 49455 192460
0 451
0 2959
0 4380
0 4902
0 9092
0 9318
0 10189
0 11109
0 13730
0 15872
0 17604
0 18557
0 19327
0 19871
0 21171
0 24112
0 26985
0 28368
0 28474
0 29569
0 30903
0 31861
0 35960
0 36791
0 38654
0 40350
0 46164
0 46921
0 47526
0 48226
0 48323
0 48592
0 49186
1 2866
1 8429
1 9731
1 98...

output:

5824
0 451
1 2866
2 171
3 10
4 1655
5 1061
6 705
7 2648
8 2167
9 2283
10 1073
11 1750
12 1158
13 3089
14 792
15 1342
16 944
17 936
18 4238
19 484
20 2165
21 637
22 1260
23 2135
24 20
25 233
26 1780
27 1319
28 4005
29 1161
30 2295
31 164
32 69
33 2048
34 5149
35 3337
36 826
37 126
38 5772
39 4356
40 ...

result:

ok OK

Test #22:

score: 0
Accepted
time: 55ms
memory: 7264kb

input:

64506 23320 150593
0 4768
0 10542
0 14842
0 20602
1 1266
1 12253
2 471
2 13145
2 14023
2 15190
2 18272
2 22689
4 8149
4 9069
6 357
6 10397
6 10869
6 16797
7 5497
7 19179
8 3468
8 6448
8 11473
8 12455
8 13155
9 751
10 11245
11 10586
11 13266
11 17148
11 20206
11 22535
12 5515
13 374
13 19047
14 11867...

output:

23290
0 10542
1 1266
2 471
4 8149
6 10397
7 19179
8 6448
9 751
10 11245
11 10586
12 5515
13 374
14 15068
15 15514
16 1166
17 12852
18 6391
20 5047
21 859
22 3062
23 9135
24 7468
25 2182
26 437
27 4491
28 1250
29 6362
30 10358
31 7475
32 21280
33 19339
34 110
35 6076
36 394
37 15801
38 2814
39 11263
...

result:

ok OK