QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#480881 | #898. 二分图最大匹配 | ItheaValgulious# | AC ✓ | 2569ms | 34716kb | C++14 | 2.1kb | 2024-07-16 19:23:59 | 2024-07-16 19:24:00 |
Judging History
answer
#include<iostream>
#include<climits>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<array>
#define endl '\n'
using namespace std;
using ll = long long;
using pi2 = array<int,2>;
using pi3 = array<int,3>;
const int N=2e5+500,M=4e5+50;
struct Edge{
int u,v,w,nxt;
} edges[M*2];
int head[N],ecnt;
void add_edge_(int u,int v,int w){
edges[++ecnt]={u,v,w,head[u]};
head[u]=ecnt;
}
void add_edge(int u,int v,int w){
add_edge_(u,v,w),add_edge_(v,u,0);
}
int cpy[N],dis[N];
bool bfs(int s,int t){
memcpy(cpy,head,sizeof(cpy)),memset(dis,0x3f,sizeof(dis));
queue<int> q;
q.push(s),dis[s]=0;
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=edges[i].nxt){
if(edges[i].w&&dis[edges[i].v]>dis[edges[i].u]+1){
dis[edges[i].v]=dis[edges[i].u]+1;
q.push(edges[i].v);
}
}
}
return dis[t]<0x3f3f3f3f;
}
ll dfs(int u,int t,int minf){
if(u==t||!minf)return minf;
ll f,flow=0;
for(int &i=cpy[u];i;i=edges[i].nxt){
if(edges[i].w&&dis[edges[i].v]==dis[edges[i].u]+1){
if(f=dfs(edges[i].v,t,min(edges[i].w,minf))){
flow+=f,minf-=f,edges[i].w-=f,edges[((i-1)^1)+1].w+=f;
if(!minf)return flow;
}else{
dis[edges[i].v]=-1;
}
}
}
return flow;
}
ll dinic(int s,int t){
ll flow=0;
while(bfs(s,t))
flow+=dfs(s,t,INT_MAX);
return flow;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n1,n2,m,s,t;
cin>>n1>>n2>>m;
s=n1+n2+1,t=s+1;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
u++,v++;
add_edge(u,v+n1,1);
}
for(int i=1;i<=n1;i++)add_edge(s,i,1);
for(int i=1;i<=n2;i++)add_edge(i+n1,t,1);
int f=dinic(s,t);
cout<<f<<endl;
for(int i=1;i<=ecnt;i++){
if(edges[i].u<=n1&&edges[i].v<=n1+n2&&edges[i].w==0){
cout<<edges[i].u-1<<" "<<edges[i].v-n1-1<<endl;
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 2569ms
memory: 23128kb
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 78474 45795 92549 13903 73460 34144 96460 92850 76342 51542 76410 89381 1778 61392 43607 96135 84268 74827 19876 174 1481 94390 12423 55019 64368 92587 81295 7902 25432 46032 7004 23282 29100 60189 70797 28664 49166 48275 56159 7961 23562 76094 4507 80396 70329 91264 41532 61133 3580 43660 44...
result:
ok OK
Test #2:
score: 0
Accepted
time: 2471ms
memory: 20284kb
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 56815 52516 40377 1757 50463 66496 15833 50879 9828 16330 80692 9962 51095 17590 90774 57492 44786 41895 3386 35478 84803 93635 90745 34876 7472 34257 36580 19532 8821 61870 41395 2585 99666 33504 90496 2775 8128 71333 85506 34046 65629 62628 15022 71577 7538 82555 64524 72576 33208 93167 531...
result:
ok OK
Test #3:
score: 0
Accepted
time: 1ms
memory: 5448kb
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: 74ms
memory: 34716kb
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 25370 25370 415 415 16796 16796 12437 12437 22155 22155 84013 84013 37307 37307 72324 72324 83703 83703 78090 78090 9375 9375 82192 82192 74694 74694 49841 49841 15798 15798 36770 36770 27645 27645 50147 50147 73191 73191 47835 47835 80563 80563 22103 22103 12751 12751 24922 24922 15168 15168...
result:
ok OK
Test #5:
score: 0
Accepted
time: 59ms
memory: 34560kb
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 59469 59469 89516 89516 87040 87040 90184 90184 83075 83075 61454 61454 33615 33615 49725 49725 99247 99247 24121 24121 73533 73533 75845 75845 84418 84418 26636 26636 67341 67341 32504 32504 5752 5752 41749 41749 33184 33184 70841 70841 98815 98815 3265 3265 57647 57647 24293 24293 89920 899...
result:
ok OK
Test #6:
score: 0
Accepted
time: 2486ms
memory: 22396kb
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 22284 45795 58734 13903 57136 34144 7548 92850 27039 51542 69265 89381 67073 61392 86159 96135 83227 74827 86884 174 27268 94390 20020 55019 45357 92587 17833 7902 55801 46032 73310 23282 89482 60189 60485 28664 2721 48275 89892 7961 24437 76094 58192 80396 28938 91264 6101 61133 70994 43660 ...
result:
ok OK
Test #7:
score: 0
Accepted
time: 2482ms
memory: 26940kb
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 4850 52516 69016 1757 85854 66496 48300 50879 83741 16330 98931 9962 38730 17590 81692 57492 5076 41895 23574 35478 61976 93635 96140 34876 64057 34257 25588 19532 99191 61870 73134 2585 60977 33504 67485 2775 79816 71333 35920 34046 16162 62628 89591 71577 91372 82555 96933 72576 92891 93167...
result:
ok OK
Test #8:
score: 0
Accepted
time: 122ms
memory: 18176kb
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 33247 33397 20397 20389 3730 3431 40713 40674 26106 25818 33018 33128 17364 17001 33979 34126 25258 25026 51002 51182 3467 3257 4615 4345 31121 31136 17105 16739 37181 37003 9414 8917 43414 43395 58110 58320 16045 15694 1286 1251 43494 43464 55702 55775 6451 6014 15976 15656 4614 4350 4367 406...
result:
ok OK
Test #9:
score: 0
Accepted
time: 108ms
memory: 16124kb
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 2493 2635 29001 29517 42481 42911 47086 47300 57204 56679 47023 47219 58952 58376 28914 29453 9637 9802 32481 33146 45305 45753 47248 47444 43315 43694 43804 44151 55644 55276 45490 45921 23721 24217 56266 55795 16283 16557 29367 29865 29554 30067 7754 8004 51233 51122 12439 12809 5051 5156 45...
result:
ok OK
Test #10:
score: 0
Accepted
time: 250ms
memory: 18940kb
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: 260ms
memory: 18772kb
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: 253ms
memory: 18808kb
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: 8ms
memory: 10092kb
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: 34ms
memory: 14660kb
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: 80ms
memory: 14244kb
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: 12536kb
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: 12ms
memory: 10388kb
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: 11076kb
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: 285ms
memory: 14764kb
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: 18ms
memory: 10912kb
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: 20ms
memory: 15664kb
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: 43ms
memory: 14912kb
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