QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #113133 | #6546. Greedy Bipartite Matching | tricyzhkx | TL | 708ms | 17428kb | C++14 | 1.7kb | 2023-06-16 15:02:22 | 2023-06-16 15:02:25 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
int n,dis,d1[100010],d2[100010],mch1[100010],mch2[100010];
bool vis[100010],in_mch[100010];
struct Edge{int u,v;}E[200010];
vector<int> G[100010];
template<typename T>
void clear(T &a){T().swap(a);}
bool bfs()
{
static queue<int> que;
dis=1e9;clear(que);
fill(d1+1,d1+n+1,0);
fill(d2+1,d2+n+1,0);
for(int i=1;i<=n;i++)
if(!mch1[i]) que.push(i),d1[i]=1;
while(!que.empty())
{
int u=que.front();que.pop();
if(d1[u]>dis) break;
for(int v:G[u])
if(!d2[v])
{
d2[v]=d1[u]+1;
if(!mch2[v]) dis=d2[v];
else d1[mch2[v]]=d2[v]+1,que.push(mch2[v]);
}
}
return dis<1e9;
}
bool dfs(int u)
{
for(int v:G[u])
if(!vis[v] && d2[v]==d1[u]+1)
{
vis[v]=1;
if(mch2[v] && d2[v]==dis) continue;
if(!mch2[v] || dfs(mch2[v])) return mch1[u]=v,mch2[v]=u,true;
}
return false;
}
void dfs2(int u)
{
if(vis[u]) return;
vis[u]=1;
for(int v:G[u]) dfs2(mch2[v]);
}
int main()
{
int q,m,ans=0;
cin>>n>>q;
for(int i=1;i<=q;i++)
{
scanf("%d",&m);
for(int j=1;j<=m;j++) scanf("%d%d",&E[j].u,&E[j].v),G[E[j].u].push_back(E[j].v);
fill(in_mch+1,in_mch+n+1,0);
while(bfs())
{
for(int k=1;k<=n;k++)
if(!mch1[k] && dfs(k)) ans++,in_mch[k]=1;
fill(vis+1,vis+n+1,0);
}
for(int j=1;j<=n;j++)
if(!mch1[j]) dfs2(j);
for(int j=1;j<=m;j++) G[E[j].u].pop_back();
auto chk1=[&](int u){return in_mch[u] && !vis[u];};
auto chk2=[&](int u){return in_mch[mch2[u]] && vis[mch2[u]];};
for(int j=1;j<=m;j++)
if(!chk1(E[j].u) || !chk2(E[j].v)) G[E[j].u].push_back(E[j].v);
fill(vis+1,vis+n+1,0);
printf("%d%c",ans," \n"[i==q]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9188kb
input:
3 4 2 1 1 1 2 2 1 1 2 2 2 1 3 3 2 1 3 3
output:
1 2 2 3
result:
ok 4 number(s): "1 2 2 3"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5784kb
input:
0 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 2ms
memory: 8344kb
input:
2 2 0 2 1 2 1 2
output:
0 1
result:
ok 2 number(s): "0 1"
Test #4:
score: 0
Accepted
time: 698ms
memory: 14760kb
input:
100000 1 200000 78475 45796 32145 46393 92550 13904 73461 34145 96461 92851 56319 77067 77530 84437 76343 51543 77507 99269 76411 89382 1779 61393 43608 96136 84269 74828 14858 35967 32085 94909 19877 175 1482 94391 12424 55020 64369 92588 81296 7903 25433 46033 36294 61129 73556 84837 8419 10215 12...
output:
100000
result:
ok 1 number(s): "100000"
Test #5:
score: 0
Accepted
time: 708ms
memory: 14036kb
input:
100000 1 200000 56816 52517 2577 76202 40378 1758 50464 66497 15834 50880 9829 16331 80693 9963 51096 17591 15871 35192 91302 65510 90775 57493 11891 8967 44787 41896 3387 35479 93471 47453 84804 93636 90746 34877 18202 38718 7473 34258 36581 19533 13249 27525 6442 69870 8822 61871 94537 67714 41396...
output:
100000
result:
ok 1 number(s): "100000"
Test #6:
score: 0
Accepted
time: 2ms
memory: 7440kb
input:
4 1 7 2 2 3 3 1 1 4 2 2 3 3 1 4 3
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 33ms
memory: 12904kb
input:
100000 1 199999 25371 25371 85965 85964 416 416 16797 16797 12438 12438 45410 45409 63006 63005 22156 22156 87829 87828 84014 84014 37308 37308 72325 72325 83704 83704 55391 55390 6781 6780 78091 78091 9376 9376 82193 82193 74695 74695 49842 49842 15799 15799 69856 69855 82949 82948 97390 97389 205 ...
output:
100000
result:
ok 1 number(s): "100000"
Test #8:
score: 0
Accepted
time: 38ms
memory: 12936kb
input:
100000 1 199999 59470 59470 76774 76773 89517 89517 87041 87041 90185 90185 83076 83076 61455 61455 33616 33616 85795 85794 92073 92072 49726 49726 63843 63842 99248 99248 24122 24122 29553 29552 73534 73534 75846 75846 27030 27029 84419 84419 26637 26637 10101 10100 75014 75013 67342 67342 75647 75...
output:
100000
result:
ok 1 number(s): "100000"
Test #9:
score: 0
Accepted
time: 634ms
memory: 13856kb
input:
100000 1 199999 22285 45796 32145 44931 58735 13904 57137 34145 7549 92851 56319 11875 77530 85279 27040 51543 77507 94258 69266 89382 67074 61393 86160 96136 83228 74828 14858 19501 32085 73640 86885 175 27269 94391 20021 55020 45358 92588 17834 7903 55802 46033 36294 46558 73556 13747 8419 88394 1...
output:
100000
result:
ok 1 number(s): "100000"
Test #10:
score: 0
Accepted
time: 686ms
memory: 17428kb
input:
100000 1 199999 4851 52517 2577 29251 69017 1758 85855 66497 48301 50880 83742 16331 98932 9963 38731 17591 15871 13961 91302 97596 81693 57493 11891 59333 5077 41896 23575 35479 93471 65246 61977 93636 96141 34877 18202 35367 64058 34258 25589 19533 13249 91004 6442 83449 99192 61871 94537 16903 73...
output:
100000
result:
ok 1 number(s): "100000"
Test #11:
score: 0
Accepted
time: 424ms
memory: 11788kb
input:
100000 1 199997 4415 9894 97824 23182 2551 30097 24322 27913 64552 31862 23073 68076 28494 14953 11400 33367 14514 13085 40869 51446 63170 88054 76550 23848 22657 57759 9479 56985 96440 59224 69954 84962 55443 22220 96520 87619 31746 72821 8800 6061 36912 77572 8970 95816 32991 68335 29931 84159 333...
output:
63398
result:
ok 1 number(s): "63398"
Test #12:
score: 0
Accepted
time: 285ms
memory: 11640kb
input:
100000 1 199998 88398 83466 84749 59029 89875 66158 13827 70123 42158 89836 17150 69739 94515 36029 65168 64957 20523 82579 767 6540 23367 32863 61341 51172 41325 62479 6019 38350 61266 36740 88694 66965 87199 74377 27532 67626 72836 38103 66474 43665 94014 82684 22393 7656 65428 88846 1268 82978 82...
output:
63828
result:
ok 1 number(s): "63828"
Test #13:
score: 0
Accepted
time: 385ms
memory: 11876kb
input:
100000 1 199999 19916 73760 33590 54291 86580 62788 16261 85328 54723 79797 99874 80572 54928 54473 89925 95257 69135 85704 7329 82391 40585 16916 72524 22756 18765 12473 44987 15352 30916 89510 35447 10869 89920 87243 50945 57679 67164 34842 72434 217 33280 11229 79543 42189 39850 20240 97438 7964 ...
output:
63525
result:
ok 1 number(s): "63525"
Test #14:
score: 0
Accepted
time: 63ms
memory: 11192kb
input:
61379 1 199943 14004 13750 24505 24348 30372 30220 27662 27462 33248 33398 38347 38158 17301 16945 50477 50644 56489 56552 46691 46950 21356 21289 3900 3660 24331 24166 8807 8306 40958 40995 15090 14814 20398 20390 30865 30801 33636 33756 20901 20809 55448 55500 4336 4041 36727 36552 16497 16096 367...
output:
37154
result:
ok 1 number(s): "37154"
Test #15:
score: 0
Accepted
time: 43ms
memory: 11516kb
input:
61352 1 199960 2271 2420 38843 39328 48789 48844 2494 2636 40184 40660 59755 59011 48981 48994 52509 52277 12893 13196 33812 34566 40261 40701 2117 2290 11743 12134 29440 29943 4257 4393 51423 51264 44696 44995 21601 22166 21667 22209 26473 26786 49980 50039 12100 12516 10540 10817 32737 33402 30808...
output:
37442
result:
ok 1 number(s): "37442"
Test #16:
score: 0
Accepted
time: 76ms
memory: 12272kb
input:
100000 1 199998 1 13806 1 33642 2 9260 2 62739 2 70692 2 78119 3 41149 4 15766 4 50060 5 96645 6 91522 7 32563 9 2551 9 11397 9 48346 10 14640 10 51058 10 79294 10 92375 11 64734 11 67021 12 7765 12 46823 12 60303 13 8750 13 27870 13 69570 13 71511 14 35685 14 42580 14 82024 15 34779 16 1976 16 6932...
output:
78404
result:
ok 1 number(s): "78404"
Test #17:
score: 0
Accepted
time: 86ms
memory: 12356kb
input:
100000 1 199998 1 28390 1 41334 1 66667 2 5985 2 15913 4 63754 4 77736 5 25016 5 30451 5 90213 6 66979 6 98910 7 63466 7 78228 7 78951 7 85423 8 1744 8 1869 8 55172 9 37583 10 26492 10 82985 11 29230 11 29812 11 33064 12 10610 12 48602 12 73299 12 95659 13 29065 13 50262 13 63187 13 68617 14 86838 1...
output:
78497
result:
ok 1 number(s): "78497"
Test #18:
score: 0
Accepted
time: 81ms
memory: 12320kb
input:
100000 1 199997 1 4358 1 35526 1 51858 2 57469 2 94928 2 96005 4 75469 5 20203 5 37103 6 32208 7 8678 7 16776 7 46814 7 75641 8 30807 9 4100 9 26455 9 49377 9 55540 9 67033 10 82363 11 11388 11 33779 11 35353 11 50534 11 54707 12 44869 12 59105 15 80529 15 90601 15 99753 16 10955 16 80520 16 87341 1...
output:
78379
result:
ok 1 number(s): "78379"
Test #19:
score: 0
Accepted
time: 4ms
memory: 9124kb
input:
77101 1 11866 5 29612 5 62771 5 65606 6 22178 6 57725 15 59633 15 68650 18 9623 19 9222 19 43356 30 19613 31 44429 33 51278 35 53197 36 20940 38 68143 39 34664 39 36433 40 71933 41 62218 42 40292 44 53543 45 22019 45 60540 48 56820 48 76082 50 18327 51 52877 51 58007 52 64710 52 66012 53 26752 53 45...
output:
8453
result:
ok 1 number(s): "8453"
Test #20:
score: 0
Accepted
time: 27ms
memory: 10736kb
input:
69830 1 148749 1 8566 1 12094 1 12609 3 778 3 8772 4 6107 4 7527 4 10597 4 12200 4 14675 4 17677 5 4644 5 15017 5 17195 7 6949 8 1744 8 7751 9 2306 9 4815 10 4469 10 12247 10 16764 10 17449 11 296 11 12044 11 13972 12 169 12 4448 12 7763 12 15834 12 15994 13 1915 13 3081 13 5650 15 30 16 1676 16 464...
output:
19684
result:
ok 1 number(s): "19684"
Test #21:
score: 0
Accepted
time: 29ms
memory: 10572kb
input:
61958 1 92222 1 23731 1 34076 1 35526 2 30469 2 61016 4 24510 4 36309 5 8062 5 45186 5 54436 6 32531 6 59289 7 10105 7 56658 11 2204 11 3107 11 33779 12 29822 12 59105 13 27898 15 18851 16 13473 16 14984 16 37132 16 40141 16 49347 16 59902 17 12877 17 32646 19 26572 22 60371 23 39981 23 41045 23 611...
output:
40194
result:
ok 1 number(s): "40194"
Test #22:
score: 0
Accepted
time: 29ms
memory: 10968kb
input:
36033 1 130375 1 1578 1 16726 1 22302 1 24559 2 5978 2 6739 2 9340 2 25295 3 763 3 6993 3 10208 3 14609 4 4 4 3003 4 25048 5 12403 5 13816 5 15863 6 4728 7 6681 7 8346 7 10058 7 13353 7 17085 8 9879 8 17894 8 21629 8 23893 9 2602 9 13005 9 19100 9 23029 10 2308 10 13012 10 15777 10 22643 12 7389 12 ...
output:
25668
result:
ok 1 number(s): "25668"
Test #23:
score: 0
Accepted
time: 10ms
memory: 9804kb
input:
99117 1 25214 1 19547 1 37952 2 13805 2 18264 2 38542 2 49320 2 64694 2 81666 2 91778 3 2160 3 8897 5 38135 6 3465 6 52632 7 85972 7 92675 8 5531 8 12992 8 35466 9 12078 9 71947 10 57521 12 75487 12 95228 13 83002 14 83430 14 85533 16 32389 16 49235 16 87160 17 70734 17 95798 18 45028 19 51285 21 38...
output:
12003
result:
ok 1 number(s): "12003"
Test #24:
score: 0
Accepted
time: 15ms
memory: 9988kb
input:
53098 1 57924 1 263 1 3337 1 7252 3 2977 4 4878 5 3404 5 8280 6 4743 7 2962 7 8902 9 5980 9 8809 10 7823 11 416 13 970 14 1059 16 3593 18 5760 19 7129 20 4462 20 9344 21 5012 21 8943 22 8415 23 5218 23 5267 23 5456 24 5699 24 8698 25 5856 26 1212 26 2831 29 3686 30 1867 30 8646 33 6956 33 7046 34 24...
output:
9415
result:
ok 1 number(s): "9415"
Test #25:
score: 0
Accepted
time: 82ms
memory: 11416kb
input:
62612 1 153201 1 1820 2 26258 2 34655 2 41967 3 9610 4 19008 4 31307 4 36055 5 36682 5 42044 5 46886 5 54124 6 35273 6 48536 7 9178 7 44478 8 11190 8 17567 8 41427 8 53725 9 13816 9 36016 9 48167 11 1145 11 2929 11 21149 11 21678 11 46646 13 39908 13 53276 14 52580 15 21090 16 39808 17 46514 18 2478...
output:
53671
result:
ok 1 number(s): "53671"
Test #26:
score: 0
Accepted
time: 9ms
memory: 10220kb
input:
95835 1 31126 8 7490 11 1814 18 1853 19 9254 22 3000 26 1650 29 7089 34 4069 34 6120 35 5652 40 10351 42 5704 44 7513 52 3935 53 4247 56 4276 56 6550 65 8186 67 10081 68 10333 74 6344 74 6433 81 8845 87 1765 88 5647 93 400 96 510 96 9565 103 10599 108 583 122 5614 123 5867 124 7064 126 4181 126 6966...
output:
10716
result:
ok 1 number(s): "10716"
Test #27:
score: 0
Accepted
time: 29ms
memory: 9628kb
input:
49455 1 192460 1 452 1 2960 1 4381 1 4903 1 9093 1 9319 1 10190 1 11110 1 13731 1 15873 1 17605 1 18558 1 19328 1 19872 1 21172 1 24113 1 26986 1 28369 1 28475 1 29570 1 30904 1 31862 1 35961 1 36792 1 38655 1 40351 1 46165 1 46922 1 47527 1 48227 1 48324 1 48593 1 49187 2 2867 2 8430 2 9732 2 9880 ...
output:
5824
result:
ok 1 number(s): "5824"
Test #28:
score: 0
Accepted
time: 26ms
memory: 11156kb
input:
64506 1 150593 1 4769 1 10543 1 14843 1 20603 2 1267 2 12254 3 472 3 13146 3 14024 3 15191 3 18273 3 22690 5 8150 5 9070 7 358 7 10398 7 10870 7 16798 8 5498 8 19180 9 3469 9 6449 9 11474 9 12456 9 13156 10 752 11 11246 12 10587 12 13267 12 17149 12 20207 12 22536 13 5516 14 375 14 19048 15 11868 15...
output:
23290
result:
ok 1 number(s): "23290"
Test #29:
score: -100
Time Limit Exceeded
input:
100000 1000 33 78475 45796 32145 46393 92550 13904 73461 34145 96461 92851 56319 77067 77530 84437 76343 51543 77507 99269 76411 89382 1779 61393 43608 96136 84269 74828 14858 35967 32085 94909 19877 175 1482 94391 12424 55020 64369 92588 81296 7903 25433 46033 36294 61129 73556 84837 8419 10215 120...
output:
33 197 311 340 497 500 644 778 1331 2256 2430 2515 2536 2758 3521 3741 3831 3859 4050 4232 4425 4819 4898 4991 5027 5162 5240 5309 5380 5493 5494 5559 5639 6041 6430 6497 7129 7215 7614 7779 7928 8169 8251 8806 8905 9067 9174 9227 9266 9301 9307 9441 9458 9726 9906 9947 10031 10133 10241 11206 11311...