QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665718 | #898. 二分图最大匹配 | Zhou_JK | AC ✓ | 118ms | 12928kb | C++23 | 1.6kb | 2024-10-22 14:56:22 | 2024-10-22 14:56:23 |
Judging History
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