QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#92217#898. 二分图最大匹配lg_zhou#AC ✓4648ms31712kbC++141.8kb2023-03-30 14:24:012023-03-30 14:24:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 14:24:05]
  • 评测
  • 测评结果:AC
  • 用时:4648ms
  • 内存:31712kb
  • [2023-03-30 14:24:01]
  • 提交

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