QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#92217 | #898. 二分图最大匹配 | lg_zhou# | AC ✓ | 4648ms | 31712kb | C++14 | 1.8kb | 2023-03-30 14:24:01 | 2023-03-30 14:24:05 |
Judging History
answer
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int maxm = 1e6+5;
const int maxn = 3e5+5;
int edge[maxm], ver[maxm], nxt[maxm], head[maxn];
int now[maxn];
int cnt = 1;
void add(int x, int y, int z){
edge[++cnt] = z, ver[cnt] = y, nxt[cnt] = head[x], head[x] = cnt;
}
int d[maxn];
int l,r,m,s,t;
bool bfs(){
queue<int> q;
memset(d,0,sizeof d);
q.push(s);
d[s] = 1;
while(!q.empty()){
int f = q.front();
q.pop();
for (int i = head[f]; i; i = nxt[i]){
int to = ver[i];
if (edge[i] && !d[to]){
q.push(to);
d[to] = d[f]+1;
if (to == t) return 1;
}
}
}
return 0;
}
int dinic(int x, int flow){
if (x == t) return flow;
int rst = flow;
for (int i = head[x]; i && rst; i = nxt[i]){
now[x] = i;
int y = ver[i], z = edge[i];
if (edge[i] && d[y] == d[x]+1){
int to = dinic(y,min(rst,z));
if (!to) d[y] = 0;
rst -= to;
edge[i] -= to;
edge[i^1] += to;
}
}
return flow-rst;
}
signed main(){
// freopen("a.in","r",stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> l >> r >> m;
for (int i = 1; i <= m; i++){
int x,y;
cin >> x >> y;
x++,y++;
add(x,y+l,1);
add(y+l,x,0);
}
s = 0, t = l+r+1;
for (int i = 1; i <= l; i++) add(s,i,1), add(i,s,0);
for (int i = l+1; i <= l+r; i++) add(i,t,1), add(t,i,0);
int maxflow = 0;
while(bfs()) maxflow += dinic(s,1e9);
cout << maxflow << endl;
for (int i = 1; i <= l; i++){
for (int j = head[i]; j; j = nxt[j]){
if (ver[j] > l && !edge[j]){
cout << i-1 << " " << ver[j]-l-1 << ' ';
}
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 4506ms
memory: 19768kb
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: 4589ms
memory: 18008kb
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 48685 1 54562 2 96282 3 43660 4 56572 5 72097 6 31793 7 12360 8 3023 9 14651 10 80163 11 12379 12 597 13 39076 14 77674 15 94527 16 85130 17 23849 18 35846 19 78842 20 26940 21 93329 22 69417 23 49345 24 65215 25 36147 26 45930 27 84619 28 76814 29 412 30 10858 31 38186 32 60852 33 64942 34...
result:
ok OK
Test #3:
score: 0
Accepted
time: 4ms
memory: 4632kb
input:
4 4 7 1 1 2 2 0 0 3 1 1 2 2 0 3 2
output:
3 1 1 2 0 3 2
result:
ok OK
Test #4:
score: 0
Accepted
time: 99ms
memory: 31668kb
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: 98ms
memory: 31712kb
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: 4648ms
memory: 19336kb
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: 4342ms
memory: 24336kb
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: 107ms
memory: 14356kb
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 10 0 11 3 12 6 13 9 14 10 15 1 16 4 17 7 18 11 19 2 20 13 21 8 28 14 29 15 30 32 31 26 32 24 33 29 34 28 35 20 36 46 39 47 41 44 44 40 45 39 46 38 57 51 58 53 59 54 60 52 61 55 64 60 66 57 70 61 71 63 79 73 80 70 83 71 84 74 85 68 86 69 87 75 89 78 90 76 91 77 96 80 104 79 107 85 113 96 126 95...
result:
ok OK
Test #9:
score: 0
Accepted
time: 117ms
memory: 13876kb
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 2 1 4 2 10 3 8 4 7 5 1 7 20 8 22 9 13 10 18 11 26 12 24 13 25 14 30 15 33 26 35 27 38 28 36 29 37 31 34 32 39 33 49 34 53 35 47 36 63 40 69 43 73 44 68 46 75 47 74 48 72 49 71 50 76 51 70 52 85 53 84 54 80 55 82 56 77 57 86 58 79 59 87 60 78 61 88 62 81 63 83 64 97 65 98 66 100 67 104 68 101...
result:
ok OK
Test #10:
score: 0
Accepted
time: 272ms
memory: 15940kb
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 78118 2 41148 3 15765 5 91521 6 32562 8 48345 9 79293 10 67020 12 71510 13 42579 14 34778 15 69322 16 57308 17 6162 18 52651 19 64579 21 24593 22 97997 23 77417 24 47998 25 24157 28 67932 29 65316 30 31954 31 19608 32 71996 34 98186 35 72885 36 89653 37 57779 39 36111 40 1530 41 6095...
result:
ok OK
Test #11:
score: 0
Accepted
time: 287ms
memory: 16752kb
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 3 63753 4 30450 5 98909 7 1868 10 33063 11 10609 12 68616 13 86837 15 77990 16 16525 18 93717 19 32559 21 15495 23 56994 25 47612 26 36458 27 33773 30 28313 31 82347 33 96004 34 35265 35 82877 36 24476 37 52477 39 94787 41 52015 42 99374 43 36190 45 52943 46 23141 48 34244 51 94147 52 ...
result:
ok OK
Test #12:
score: 0
Accepted
time: 271ms
memory: 15928kb
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 1 57468 3 75468 6 46813 7 30806 8 26454 10 54706 11 59104 14 80528 16 32645 19 49350 20 58977 21 31926 22 50244 23 5726 24 92464 26 52648 27 57836 28 96888 30 50525 31 76950 32 73647 33 971 35 81872 36 660 37 65791 38 55672 39 29124 41 27121 44 77986 46 2959 48 91397 51 66821 52 87844 54 77781...
result:
ok OK
Test #13:
score: 0
Accepted
time: 2ms
memory: 9252kb
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 65605 5 57724 14 68649 17 9622 18 43355 29 19612 30 44428 32 51277 34 53196 35 20939 37 68142 38 36432 39 71932 40 62217 43 53542 44 60539 47 76081 50 58006 51 66011 52 45116 54 5453 55 72966 57 8366 58 70074 59 16851 60 59385 62 16210 67 18050 68 27089 70 47489 71 41622 73 59911 74 70531 76 ...
result:
ok OK
Test #14:
score: 0
Accepted
time: 47ms
memory: 11148kb
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 668 6774 847 606 1602 11215 1618 5082 2193 14844 2356 13543 2615 17856 3482 1570 3603 7499 3758 6608 3880 2324 4703 14155 4731 16394 5166 2647 5174 2124 5205 4310 5214 439 5217 11249 5510 1121 5648 7433 5678 720 5680 5562 5808 1941 5903 1332 5985 4567 6002 2875 6535 10687 6924 8314 6977 8736 7...
result:
ok OK
Test #15:
score: 0
Accepted
time: 48ms
memory: 10616kb
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 34075 1 61015 3 24509 4 45185 5 59288 11 29821 12 27897 15 37131 16 12876 21 60370 22 41044 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 39 53021 42 10909 43 28881 45 10878 47 25324 49 28754 50 41229 52 41546 53 39764 54 24...
result:
ok OK
Test #16:
score: 0
Accepted
time: 65ms
memory: 9868kb
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 1577 4 15862 7 9878 25 10609 29 9367 31 1566 33 11274 37 165 52 4696 54 18108 55 11897 80 6783 92 17184 96 3321 106 1856 107 16666 108 23586 115 12674 116 13458 121 14106 123 4546 124 4942 127 794 131 9058 133 4574 138 3450 142 8704 150 7379 155 14162 159 6829 163 6665 166 10404 169 2412 180...
result:
ok OK
Test #17:
score: 0
Accepted
time: 6ms
memory: 8860kb
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 37951 1 91777 2 8896 4 38134 5 52631 6 92674 7 35465 8 12077 9 57520 11 95227 12 83001 13 85532 15 87159 16 95797 17 45027 18 51284 20 59547 21 5520 23 86112 26 29339 27 18534 28 31861 30 49493 33 30727 34 40008 37 81810 38 72113 39 11712 40 81311 41 75321 43 49309 44 83232 46 77294 47 92399...
result:
ok OK
Test #18:
score: 0
Accepted
time: 18ms
memory: 8192kb
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 78 2123 98 1545 192 8384 415 908 848 1206 945 2497 1133 51 1644 4440 1883 1987 2635 1286 2673 981 3029 157 3043 211 3313 3513 3548 7190 3782 5055 3892 4661 3984 375 4002 341 4007 6676 4105 7457 4172 533 4189 252 4390 4566 4497 7011 4666 1763 4681 8771 4707 4379 4746 5111 4798 2134 4854 5527 501...
result:
ok OK
Test #19:
score: 0
Accepted
time: 230ms
memory: 12268kb
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 1 41966 3 31306 4 36681 6 9177 7 41426 8 48166 10 1144 15 39807 16 46513 17 57314 18 53192 20 58031 22 30788 24 43728 27 53143 28 60322 29 45277 30 49076 31 16727 32 22621 33 6527 34 57171 36 9660 37 13583 38 10615 39 28697 43 43072 44 15631 45 39372 46 34156 47 3233 48 18899 50 24067 51 16032...
result:
ok OK
Test #20:
score: 0
Accepted
time: 23ms
memory: 9148kb
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 123 7063 137 7604 144 3682 188 4648 197 4971 262 8971 264 111 334 10609 364 7311 386 8103 394 3910 524 6307 540 10058 564 3602 581 4078 629 5299 653 6060 660 4249 669 4906 679 4647 752 5229 762 2742 869 2933 922 2489 927 1545 951 7734 968 580 1004 8125 1047 5593 1066 6281 1222 7310 1264 3838 1...
result:
ok OK
Test #21:
score: 0
Accepted
time: 28ms
memory: 10888kb
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 46164 1 42273 2 43936 3 44252 4 38734 5 43336 6 45637 7 43357 8 45814 9 41048 10 47432 11 44981 12 44043 13 44199 14 42833 15 42083 16 43133 17 44171 18 43692 19 43727 20 39500 21 41663 22 43741 23 42841 24 43640 25 46018 26 43841 27 44651 28 48500 29 42882 30 46279 31 43862 32 44382 33 45960...
result:
ok OK
Test #22:
score: 0
Accepted
time: 50ms
memory: 11144kb
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 70 16298 280 2648 358 19371 476 4120 557 15534 627 16034 660 20221 798 16539 815 2041 821 5172 856 4403 927 18662 945 5500 1122 648 1182 18410 1191 15540 1192 2738 1252 4864 1269 8726 1275 122 1319 4352 1354 18142 1445 338 1605 15744 1639 375 1705 7772 1734 19530 1984 4314 2063 12763 2150 5016...
result:
ok OK