Description

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

n,m≤1000

因为数据有坑，可能会遇到 v>m 或者 u>n 的情况。请把 v>m 或者 u>n 的数据自觉过滤掉。

算法：二分图匹配

data

# 12

input

6 5 5
1 2
2 3
3 4
1 5
5 6

output

3

wrong

4

# large_hack

input

570 65 553
955 96
14 31
320 76
777 118
739 2
655 82
424 75
954 100
701 17
1102 61
763 32
147 4
567 42
346 78
597 103
83 54
419 52
86 40
689 30
656 118
292 85
200 102
153 44
811 103
811 0
285 72
967 50
5 95
723 117
1063 126
156 18
240 24
609 91
669 56
805 51
864 55
892 28
891 6
761 127
526 80
382 44
216 128
709 48
757 28
1014 60
574 108
216 83
148 115
932 25
601 118
875 20
428 11
876 100
312 1
46 63
568 81
1131 78
302 89
437 5
517 61
1076 2
31 38
84 16
634 49
296 51
417 23
156 36
530 58
39 36
319 39
260 90
401 19
297 46
777 34
1080 40
374 72
45 51
853 54
425 46
648 34
238 88
920 37
107 63
176 128
541 65
1047 23
1033 18
737 41
0 95
179 60
625 92
119 39
1090 49
170 126
394 127
120 24
917 25
639 59
388 60
236 119
38 20
38 13
1047 64
1020 14
1013 121
1001 107
140 102
266 64
622 85
812 88
767 61
843 77
853 17
942 73
27 74
572 57
803 115
562 8
338 30
537 63
1035 13
915 74
298 123
585 90
518 84
472 20
548 28
449 103
347 60
893 49
521 16
308 88
47 3
140 22
852 67
410 14
102 1
405 17
582 65
429 50
721 104
238 118
70 48
709 3
309 128
699 81
453 55
430 57
739 5
884 50
459 84
197 94
30 79
1098 60
80 77
982 122
967 51
62 36
728 28
961 47
42 59
1130 111
583 70
624 80
785 124
293 56
954 86
442 99
120 53
623 93
961 29
436 81
756 68
747 49
714 78
383 100
859 68
384 75
1040 60
716 112
723 129
461 121
902 56
951 91
603 2
588 90
171 41
247 67
785 21
502 57
689 63
280 1
742 75
58 1
443 116
372 90
561 129
882 65
1070 105
551 98
920 114
33 19
841 78
574 88
693 35
404 48
680 78
396 120
590 6
320 49
464 92
536 76
681 113
473 64
162 62
457 8
1121 36
254 103
904 107
575 110
732 75
71 8
611 62
27 123
775 23
201 105
976 53
10 102
93 37
142 32
782 6
326 97
205 47
271 126
1058 54
972 113
363 96
267 19
67 94
884 85
30 125
699 26
370 65
565 57
141 100
216 117
315 109
506 71
641 21
803 23
782 103
54 35
269 23
38 39
1099 89
1105 39
298 68
532 42
354 34
424 96
819 112
737 51
364 34
925 40
399 78
559 89
884 37
1068 81
606 55
974 122
1123 78
392 11
715 73
413 113
573 129
1048 59
457 104
579 100
149 52
770 89
366 66
823 66
985 0
588 29
738 85
960 61
52 66
574 22
210 124
738 67
302 87
641 65
886 106
55 99
539 54
799 22
638 63
1131 100
16 123
144 40
670 127
720 18
1113 69
1042 52
602 26
503 72
1021 54
379 62
575 1
301 8
309 19
470 18
228 18
174 36
573 7
265 5
754 64
690 117
354 66
478 95
667 114
83 58
130 115
141 126
35 32
469 17
732 58
812 124
774 114
334 95
297 19
475 54
548 0
142 110
851 17
532 95
642 31
443 35
946 124
1084 47
1002 59
826 50
722 4
125 83
1139 122
573 121
463 102
142 27
226 33
923 101
197 2
158 18
1138 72
244 20
424 14
1081 3
125 31
506 25
525 59
264 34
1084 72
972 31
1131 71
202 35
627 126
298 58
1023 92
694 32
515 124
984 123
297 111
418 8
390 36
47 82
892 6
387 101
167 91
1031 5
562 113
2 9
339 86
651 57
186 76
224 67
930 44
1039 74
496 62
367 75
19 116
550 103
484 31
604 111
1127 48
254 87
651 126
751 35
315 81
102 30
164 116
654 12
881 86
751 93
585 40
906 66
972 64
546 70
748 18
344 27
797 38
984 23
646 125
637 8
422 21
723 17
499 88
603 11
651 81
170 110
928 35
449 72
732 36
269 90
1040 102
1131 33
332 20
982 73
1124 122
556 106
877 53
613 53
947 125
1106 47
281 106
493 65
62 63
94 60
1107 40
217 115
85 30
941 72
680 66
292 101
331 111
108 75
810 55
978 18
602 87
764 117
749 90
28 128
742 93
223 106
277 60
896 78
1061 20
721 30
829 101
658 71
682 45
460 41
1135 2
1036 41
1058 65
593 35
514 86
243 57
1088 93
217 126
747 87
504 52
819 36
416 59
436 27
672 55
826 17
53 120
832 1
1124 99
967 18
897 23
400 113
302 116
257 128
147 30
516 73
957 54
396 23
954 41
616 0
70 6
453 103
327 20
367 125
150 23
43 127
391 128
412 70
776 52
192 13
807 112
240 101
437 111
174 43
271 85
1137 33
1135 88
606 85
550 81
1114 59
1001 20
1056 51
1056 5
345 66
811 99
189 41
1107 101
896 91
547 101
1040 121
707 35
684 97
164 73
265 2
1002 105
817 112
286 34
706 101
185 74
343 98
401 75
316 109
972 1
970 84
322 15
942 35
1026 94
568 51
269 121
879 10
374 129
694 59
318 98
759 10
584 84
899 0
102 56
274 112
434 41
997 115
763 74
297 41
419 81
169 110

output

59

wrong

24

# small_hack

input

7 5 4
3 4
2 9
9 3
1 7

output

1

wrong

2

std

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int match[1100000],last[1100000],len,n,m,k,x,y,ans;
bool cow[1100000];
struct note{
    int x,y,next;
}a[1100000];
void add(int x,int y)
{
    ++len;
    a[len].x=x;
    a[len].y=y;
    a[len].next=last[x];
    last[x]=len;
}
bool check(int x)
{
    for(int i=last[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(cow[y])
        {
            cow[y]=false;
            if (match[y]==0||check(match[y])==true)
            {
                match[y]=x;
                return true;
            }
        }
    }
   return false;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i)
    {
        scanf("%d%d",&x,&y);
        if(x>n||y>m) continue;
        add(x,y); 
    }
    for(int i=1;i<=n;i++)
    {
        memset(cow,true,sizeof(cow));
        if(check(i))
            ans++;
    }
    printf("%d",ans);
    return 0;
}