首页 > 代码库 > usaco-4.1-stall4-passed
usaco-4.1-stall4-passed
这个题是最有意思的了，一次性通过，网络流，最大流法，匈牙利法，网上有一篇趣写算法系列－－趣写算法系列之--匈牙利算法
这是我见过很有趣的东东了，推荐给大家，
/*ID: qq104801LANG: C++TASK: stall4*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>using namespace std;const int inf=0xfffffff;const int nmax=205;int n,m,ans;int a[nmax][nmax];int v[nmax],girl[nmax];bool find(int x){ int i,j; for(j=1;j<=m;j++) if(a[x][j] && !v[j]) { v[j]=1; if(girl[j]==0 || find(girl[j])) { girl[j]=x; return true; } } return false;}void test(){ freopen("stall4.in","r",stdin); freopen("stall4.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i][0]; for(int j=1;j<=a[i][0];j++) { int t; cin>>t; a[i][t]=1; } } for(int i=1;i<=n;i++) { memset(v,0,sizeof(v)); if(find(i))ans+=1; } cout<<ans<<endl; }int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 12 users onlineCHN/2 IDN/1 IND/1 MAC/1 SWE/1 USA/4 VNM/2USER: cn tom [qq104801]TASK: stall4LANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.003 secs, 3540 KB] Test 2: TEST OK [0.003 secs, 3540 KB] Test 3: TEST OK [0.003 secs, 3540 KB] Test 4: TEST OK [0.003 secs, 3540 KB] Test 5: TEST OK [0.011 secs, 3540 KB] Test 6: TEST OK [0.016 secs, 3540 KB] Test 7: TEST OK [0.016 secs, 3540 KB] Test 8: TEST OK [0.016 secs, 3540 KB] Test 9: TEST OK [0.016 secs, 3540 KB]All tests OK.YOUR PROGRAM (‘stall4‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----1 00------- test 2 ----5 51 11 21 31 41 5------- test 3 ----5 52 2 53 2 3 42 1 53 1 2 51 2------- test 4 ----10 103 1 7 83 5 9 103 3 6 103 5 6 93 4 5 83 1 8 102 3 82 4 83 2 3 63 4 6 7------- test 5 ----15 152 12 132 1 112 8 122 7 92 12 152 6 82 5 122 12 142 10 122 3 42 11 132 10 112 8 152 8 152 13 14------- test 6 ----50 502 12 302 18 432 11 462 30 372 25 282 2 492 26 362 3 272 23 502 2 502 17 222 47 482 8 112 41 492 6 182 18 432 36 482 8 362 22 312 6 372 39 492 5 252 25 312 24 272 4 271 252 21 432 1 232 22 312 37 422 35 402 5 372 20 402 1 452 11 322 6 102 10 202 34 442 10 402 18 442 37 422 19 292 13 412 30 442 13 212 2 302 5 342 25 382 23 332 25 34------- test 7 ----150 15013 14 24 52 72 75 89 90 92 108 121 128 131 14213 10 18 29 35 36 41 60 68 83 102 107 137 14013 22 31 45 83 91 94 96 98 106 113 114 117 11912 2 22 34 46 66 69 80 89 108 116 128 13013 3 8 10 46 59 67 70 75 90 106 120 137 14813 3 7 31 36 40 42 51 62 85 88 90 101 12013 9 25 27 28 40 48 84 97 100 101 109 116 13112 2 8 20 34 52 64 69 94 109 118 137 14713 20 50 65 92 97 111 116 117 119 120 126 139 14612 37 46 54 55 80 103 113 121 140 144 146 14813 17 40 51 54 67 82 86 92 93 107 117 148 15011 4 33 46 47 117 119 132 142 143 149 15012 35 47 55 71 82 90 112 120 121 122 125 13913 10 13 18 28 44 49 56 58 60 87 122 129 14013 5 24 31 46 51 55 65 75 92 100 131 133 14512 34 39 51 78 81 88 98 110 114 122 134 13812 13 18 39 45 68 76 92 94 95 107 113 12413 21 22 35 37 41 43 49 91 93 109 132 137 14912 5 8 49 75 76 88 102 105 113 119 126 14212 6 23 32 65 67 80 98 101 114 121 125 14212 11 21 42 53 61 69 79 86 90 114 115 12313 12 14 24 28 50 51 55 83 87 92 114 115 11813 3 4 13 31 59 83 85 96 101 103 128 144 14912 41 51 59 65 90 100 108 111 113 122 133 14113 13 16 18 50 54 64 88 98 102 115 119 123 12413 22 39 43 44 48 89 93 100 104 107 121 132 13713 4 12 35 52 53 80 90 109 120 131 132 141 14713 23 37 60 61 72 85 94 103 116 119 137 144 14513 19 21 35 37 53 73 84 91 111 116 119 125 14811 5 9 27 31 59 101 118 125 135 140 14913 10 12 31 56 62 69 70 71 88 89 105 128 14113 3 29 53 57 64 82 84 88 96 112 114 115 14911 21 32 38 63 73 75 103 120 125 131 13813 11 15 20 25 45 78 82 94 109 125 132 133 13413 14 21 44 70 82 90 108 111 128 134 141 143 14512 14 45 83 87 90 93 95 103 116 125 134 13913 10 27 35 44 69 77 78 80 87 93 95 109 13712 30 34 39 41 48 54 73 74 79 129 131 14613 6 17 20 33 43 79 83 88 96 110 113 122 13713 22 25 36 46 59 70 84 93 95 98 119 123 14313 6 10 13 39 56 67 75 78 81 115 123 127 13712 9 13 23 25 30 45 66 94 103 133 140 14913 13 35 45 67 72 83 90 107 117 121 125 145 15013 5 30 70 80 83 90 92 101 112 114 126 132 13713 9 21 37 38 43 65 68 70 81 88 98 110 13613 10 13 32 57 58 90 93 94 95 108 109 113 14812 5 8 18 39 43 45 53 85 88 108 126 13413 1 38 42 59 70 81 94 121 122 124 131 135 14713 2 5 41 65 76 90 91 95 102 119 121 138 14812 11 27 32 42 60 79 82 108 112 126 136 13811 8 35 52 63 83 94 96 99 101 132 15013 15 45 57 58 73 84 89 98 99 100 128 129 13311 6 65 69 78 88 111 122 126 130 132 15012 15 24 42 50 56 63 94 99 114 116 124 14911 4 20 48 63 86 87 88 97 111 143 14913 20 21 38 41 67 74 77 98 100 107 121 132 13613 15 27 41 46 63 75 78 82 104 117 119 126 14313 8 36 53 55 68 81 83 97 103 107 133 138 14013 1 16 18 24 30 32 43 88 106 108 110 136 14413 5 38 48 51 58 79 89 97 103 120 125 137 14313 15 19 25 30 44 45 60 66 83 90 92 102 13712 39 46 57 61 103 105 109 119 122 128 135 14013 10 14 33 38 54 68 82 99 101 106 126 135 13913 1 16 35 59 69 83 105 115 117 121 128 136 13913 17 21 25 26 27 29 32 34 58 62 79 94 12213 11 20 35 49 50 83 94 109 123 125 131 139 15012 24 26 33 43 69 96 102 118 124 127 147 14812 13 19 31 37 43 54 71 83 86 102 131 14213 15 18 35 41 61 65 67 84 91 95 98 118 13912 21 33 51 57 61 70 87 93 103 106 107 14713 1 28 31 32 33 50 72 87 97 99 117 118 13013 9 11 13 34 42 61 63 67 69 74 75 111 12613 1 18 45 48 79 88 93 100 104 114 120 137 14612 11 12 20 23 24 64 72 85 87 89 99 12012 21 35 64 83 87 107 114 119 126 135 138 14313 2 7 13 19 21 64 65 89 90 102 111 140 14713 3 11 24 25 28 33 35 48 49 70 82 122 14313 7 12 55 58 62 65 95 105 110 115 119 120 14113 4 7 16 21 23 28 40 43 48 75 83 133 13712 32 35 36 55 68 71 73 76 82 116 127 14412 28 30 33 36 48 63 66 96 111 113 133 14011 2 49 70 79 101 102 129 135 137 138 14511 24 34 35 52 57 62 75 110 134 147 14912 5 23 53 57 66 72 92 117 137 141 142 14713 4 31 34 55 58 77 81 82 85 89 116 133 14012 46 52 55 59 74 92 109 121 134 138 142 14512 4 23 26 39 59 66 77 84 108 120 136 14712 4 26 39 40 46 72 82 100 123 130 131 14413 1 17 26 41 64 79 86 94 103 106 112 120 14612 11 14 70 73 92 94 106 109 113 132 144 14512 1 6 8 12 19 36 52 78 94 95 112 11713 2 10 19 30 45 56 75 81 83 102 125 135 14913 1 13 45 46 49 52 63 83 85 92 115 140 14412 21 42 55 57 72 84 90 91 96 121 147 14811 17 41 54 55 65 93 99 105 114 140 14312 3 26 27 28 32 39 69 87 104 111 113 11713 22 34 47 57 73 83 84 85 88 102 137 138 14312 4 15 20 53 80 83 86 92 105 114 126 13213 1 13 34 46 71 75 83 84 102 116 131 132 14512 5 23 37 45 55 58 70 76 82 90 125 14212 27 52 57 72 77 93 97 98 123 131 134 13612 4 19 39 48 49 50 58 70 85 93 108 13212 8 21 24 40 48 81 97 98 100 131 145 14813 21 22 39 52 54 71 72 78 102 116 120 126 13213 11 39 51 56 58 60 63 67 96 106 117 129 14712 9 13 14 25 47 56 115 126 134 136 145 14712 1 14 57 69 77 78 91 92 109 112 135 14712 45 59 64 72 81 87 92 103 105 128 133 13712 20 55 56 58 69 70 71 83 111 117 120 14411 10 16 29 43 65 66 83 88 96 108 14711 19 43 45 52 67 83 106 111 116 133 14513 18 22 24 30 38 46 57 69 73 78 83 126 13613 2 19 22 59 63 64 75 84 92 106 126 134 13613 16 30 34 38 53 54 75 82 130 132 134 145 14812 4 19 44 84 91 95 110 113 115 116 130 13111 9 34 49 58 64 74 76 83 103 121 14513 14 17 30 51 53 64 73 90 93 107 110 117 14313 6 8 29 33 40 50 77 103 108 111 124 130 15013 4 11 21 23 31 42 80 85 91 114 121 124 14113 6 35 43 51 58 63 76 84 104 108 127 144 15013 9 10 14 46 62 70 81 94 102 107 111 135 14912 5 22 31 54 55 69 76 87 98 99 129 13413 5 13 15 24 33 50 95 103 106 120 121 147 14913 10 21 25 26 31 38 46 80 83 99 106 111 14213 2 14 25 28 47 59 76 78 81 111 114 125 13313 3 5 25 32 42 72 73 77 97 108 134 139 14513 15 16 24 30 39 40 64 94 105 110 112 119 13713 12 30 37 44 49 68 86 114 115 126 129 138 14512 13 28 36 60 83 84 89 96 110 123 133 14611 10 15 26 55 59 66 71 74 83 107 11013 7 39 46 62 63 66 74 76 81 90 102 118 13413 8 38 48 52 75 79 81 112 113 123 134 148 14913 41 48 56 62 72 77 96 106 118 123 128 140 14511 2 15 22 54 60 81 100 117 118 119 13413 14 20 30 36 47 51 69 99 102 118 132 137 14613 5 7 14 28 32 48 69 74 95 101 131 132 13912 5 50 72 84 85 86 104 106 119 135 136 14913 1 16 17 23 36 41 71 84 117 118 136 137 14813 6 10 12 48 64 85 99 112 125 129 130 141 14612 5 33 36 80 106 116 130 132 134 139 147 15013 9 35 41 50 52 75 101 121 123 127 132 133 14812 16 41 48 60 67 72 88 100 110 138 142 14512 4 21 30 37 85 87 92 96 105 133 136 15012 28 39 56 61 91 102 111 123 131 132 141 14612 8 20 42 53 62 68 71 77 99 101 127 13813 3 8 19 20 30 35 37 38 63 119 131 134 14212 32 67 70 93 102 105 111 120 129 130 137 14913 29 31 41 44 49 57 73 75 99 107 110 117 14413 15 32 33 40 51 52 53 72 74 114 119 141 14413 10 14 42 48 49 85 89 93 103 105 117 119 144------- test 8 ----200 2003 54 150 1543 52 126 1753 22 145 1763 87 94 1603 18 20 1133 15 39 523 77 102 1793 68 77 1893 138 153 1763 66 97 1373 50 119 1442 94 1023 19 47 1163 75 133 1953 88 95 1513 1 3 1333 15 35 793 112 147 1933 64 84 1813 21 157 1603 10 23 1653 58 111 1413 35 77 1573 72 90 1503 25 40 1593 42 119 1603 52 121 1743 67 86 1673 148 151 1983 61 105 1723 21 128 1363 30 69 1943 70 103 1413 53 98 1413 77 100 1883 27 60 1963 33 47 693 133 190 2003 56 130 1483 7 53 1913 11 178 1803 41 48 1143 107 150 1823 3 79 1763 66 79 1173 16 75 933 75 121 1623 54 108 1523 7 108 1833 14 56 1733 108 184 1923 25 87 1053 7 11 1343 84 85 1873 86 103 1513 44 119 1653 6 39 1943 102 157 1603 10 13 1643 65 177 1953 168 169 1723 59 73 1523 84 177 1923 70 76 1833 68 161 1733 19 92 1263 62 85 1643 68 123 1873 24 135 1963 61 130 1883 32 98 1653 50 90 1333 6 26 823 8 89 1583 76 119 1583 44 94 1313 7 22 1563 23 106 1303 47 65 933 34 88 1943 92 149 1993 131 141 1803 70 136 1663 24 152 1743 49 109 1823 27 113 1423 70 98 1343 40 77 1203 6 132 1673 1 20 703 64 168 1993 129 148 1563 18 65 963 62 89 1693 36 71 783 85 105 1833 27 116 1753 51 124 1553 43 57 873 10 107 1273 10 74 1903 8 21 1463 39 41 1373 1 7 1033 85 89 1393 23 160 1893 49 142 1633 14 57 1723 12 15 713 24 99 1973 5 33 1873 41 78 1323 99 173 1773 75 137 1773 13 66 1443 25 28 353 17 84 1663 23 55 1803 35 70 1933 63 94 1333 60 127 1373 15 46 1673 113 143 1773 50 120 1493 24 185 1933 10 21 373 37 72 1753 17 155 1982 10 323 73 79 1653 101 132 1723 98 115 1773 28 65 1533 7 77 1023 70 125 1263 90 111 1613 32 120 1273 95 144 1873 93 153 1963 25 75 1243 47 89 1563 132 145 1893 9 85 1043 15 131 1873 8 112 1413 51 73 773 105 167 1713 65 91 943 37 86 1573 81 161 1903 7 14 1693 151 158 1693 61 101 1593 174 186 1913 114 173 1993 75 84 1653 42 136 1563 60 135 2003 151 157 1723 37 38 1613 7 174 1973 3 143 1643 25 44 1533 16 30 1123 2 14 853 85 88 1993 41 129 1643 64 99 1013 35 51 993 56 88 1963 84 94 1703 86 100 1123 39 63 1563 87 151 1853 35 102 1863 34 71 1163 3 112 1983 12 97 1322 63 1963 31 51 1503 26 33 1443 44 119 1952 107 1583 62 108 1933 47 95 1433 10 32 1773 13 103 1743 14 71 1453 25 66 1403 88 117 1703 37 61 1963 70 104 1913 10 98 1893 3 147 1603 6 54 983 37 108 1973 120 140 1733 65 147 1533 5 18 1783 65 83 175------- test 9 ----200 2006 51 81 152 166 174 1945 6 21 66 161 1706 36 52 104 150 157 1986 16 35 102 122 153 1546 84 105 117 128 145 1476 32 43 77 149 182 1976 6 11 69 109 119 1396 18 32 136 171 175 1816 29 125 127 136 152 1606 1 73 78 106 133 1906 60 67 92 110 114 1176 18 62 87 97 108 1806 54 80 88 105 119 1205 6 25 35 55 1505 14 45 79 109 1685 4 70 104 109 1956 92 150 170 179 197 1996 5 69 83 86 123 1886 59 65 67 73 96 1476 5 19 21 74 107 1436 16 22 23 91 119 1246 18 44 66 70 94 1096 34 108 112 135 148 1936 2 56 74 77 181 1986 55 63 81 99 121 1816 11 83 99 121 173 1956 13 22 80 116 121 1456 21 28 29 71 93 1596 18 29 74 84 103 1046 41 57 83 137 161 1946 38 60 105 110 139 1406 38 59 71 117 150 1756 4 66 87 95 134 1876 15 44 105 108 179 1925 29 146 152 173 1936 5 75 132 166 168 1916 11 38 61 64 96 1806 93 106 134 171 175 1996 73 82 86 107 150 1906 16 24 96 125 140 1686 90 135 138 148 165 1686 3 10 39 140 144 1996 7 12 41 115 171 1736 46 56 63 67 113 1866 13 83 140 152 159 1646 55 120 126 136 172 1796 63 64 80 119 194 1976 37 48 62 72 91 1876 34 101 106 118 163 1935 3 40 127 169 1756 9 47 101 108 181 1826 34 91 95 117 171 1966 5 92 105 114 127 1756 8 66 84 109 183 1906 85 120 145 148 151 1586 39 46 73 92 93 1326 10 43 87 185 190 1936 39 99 103 104 148 1786 79 87 112 123 151 1696 15 70 96 143 154 1956 25 47 61 93 120 1536 32 63 72 93 109 1456 9 62 94 113 115 1926 13 23 62 78 101 1926 4 15 73 108 122 1356 4 108 132 134 158 1826 31 66 79 110 123 1946 31 42 115 119 124 1806 9 22 71 100 142 1656 83 99 103 172 187 1915 26 60 63 94 1126 17 20 28 86 106 1866 16 56 65 107 134 1416 13 49 64 135 165 1866 7 13 17 57 85 1116 13 43 73 119 135 1376 40 121 138 146 162 1826 67 78 95 131 133 1626 38 45 59 86 131 1976 9 98 129 148 155 1856 22 28 73 86 94 1646 29 71 107 125 126 1496 32 86 104 126 164 1736 27 29 93 97 141 1856 24 125 133 143 158 1716 47 126 134 154 170 1996 8 24 59 75 84 1655 41 73 78 110 1386 8 20 35 62 169 1826 7 49 56 65 85 1326 18 65 119 149 179 1816 52 62 70 111 140 1636 13 57 73 76 145 1486 35 53 92 111 114 1756 42 60 115 160 166 1746 33 38 56 74 96 1156 6 59 84 120 136 1946 9 22 69 82 94 1536 12 39 101 135 153 1696 11 127 137 171 184 1876 22 51 77 83 102 1976 7 56 71 160 166 1976 12 29 78 110 164 1726 10 13 44 73 162 1736 7 23 55 75 84 896 29 41 105 173 177 1916 44 50 89 102 123 1576 5 25 34 49 61 776 15 31 70 177 187 1976 8 44 65 66 140 1536 38 73 89 101 116 1986 6 49 108 132 160 1826 43 64 67 97 98 1746 64 103 118 134 161 1915 34 87 94 100 1596 15 74 91 99 128 1736 35 80 88 103 136 1876 6 17 32 51 59 1486 51 126 156 166 169 1906 9 21 63 90 123 1906 63 102 119 133 136 1936 1 8 15 36 71 1216 51 87 144 145 176 1996 18 50 60 70 146 1816 80 92 101 102 182 1916 20 44 85 93 153 1826 5 13 59 179 188 1946 45 89 131 145 156 1946 18 44 57 93 111 1596 49 111 158 190 191 2006 30 74 83 91 111 1676 46 51 52 63 172 1856 40 53 71 84 109 1406 20 37 100 128 142 1815 44 118 121 131 1956 12 74 107 122 147 1906 34 44 128 157 184 1996 52 83 113 143 167 1956 36 94 103 114 123 1366 44 71 135 140 154 1645 51 97 167 176 1786 51 80 114 123 196 1986 15 39 51 57 122 1636 23 40 88 137 182 1876 47 95 114 138 176 1806 24 77 92 102 143 1916 54 114 135 140 164 1746 24 95 127 142 168 1746 61 75 78 118 163 1826 11 58 60 84 97 1956 45 97 102 106 130 1746 33 118 120 147 184 2006 91 124 168 185 191 1975 65 126 130 143 1676 9 61 68 157 182 1876 52 70 79 103 168 1745 23 56 97 114 1996 15 52 106 156 166 1766 21 41 57 90 146 1836 23 43 155 173 187 2006 33 37 98 155 168 1966 48 83 85 120 151 1756 3 27 47 62 81 1676 2 23 26 43 57 1146 68 69 73 100 123 1686 27 36 60 72 140 1456 23 26 38 70 144 1575 98 107 132 153 1596 4 68 154 155 161 1766 29 40 66 97 144 1686 11 67 126 150 165 2005 69 72 94 144 1876 34 76 94 152 163 2006 82 106 147 192 195 1986 14 26 27 92 123 1824 21 51 87 1026 13 38 51 81 158 1816 14 56 90 107 174 1756 32 45 82 85 99 1266 31 40 59 109 113 1396 4 30 60 118 132 1476 11 20 40 159 161 1826 14 24 56 131 188 2005 29 30 74 114 1456 19 58 111 132 171 1976 26 31 50 157 168 1786 132 137 139 158 171 1766 14 143 158 166 177 1906 35 90 97 126 159 1886 89 93 99 118 131 1996 71 101 115 132 134 1676 10 36 45 105 109 1686 10 21 125 139 144 1786 40 76 84 97 166 1866 3 95 99 111 165 1826 6 66 92 128 196 1996 36 77 81 86 104 1396 53 60 102 111 116 1786 12 65 97 100 116 1736 30 77 83 86 96 125Keep up the good work!Thanks for your submission!
usaco-4.1-stall4-passed
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。