首页 > 代码库 > usaco-3.3-fence-pass
usaco-3.3-fence-pass
euler公式，本以为很容易通过，但是边界条件要注意，呵呵。
还有，不需要vis数组控制访问与否。
/*ID: qq104801LANG: C++TASK: fence*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>using namespace std;#define nmax 501int g[nmax][nmax];int degree[nmax];int vis[nmax][nmax];stack<int>ans;int ff;int minx;inline int max(int a,int b){ return a>b?a:b;}void euler(int u){ for(int v=1;v<=minx;v++) if(g[u][v]) // && !vis[u][v]) { vis[u][v]=1; g[u][v]--; g[v][u]--; euler(v); //cout<<"u:->v: "<<u<<" "<<v<<endl; } ans.push(u);}void test(){ freopen("fence.in","r",stdin); freopen("fence.out","w",stdout); cin>>ff; int x,y; minx=0; for(int i=0;i<ff;i++) { cin>>x>>y; g[x][y]++; g[y][x]++; degree[x]++; degree[y]++; minx=max(minx,x); minx=max(minx,y); } //cout<<minx<<endl; bool find=false; for(int i=0;i<=minx;++i) if(degree[i]%2==1) { find=true; euler(i); break; } if(!find)euler(1); while(!ans.empty()) { cout<<ans.top()<<endl; ans.pop(); }}int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 14 users onlineCHN/3 IND/4 MYS/1 USA/6USER: cn tom [qq104801]TASK: fenceLANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.005 secs, 5468 KB] Test 2: TEST OK [0.005 secs, 5468 KB] Test 3: TEST OK [0.005 secs, 5468 KB] Test 4: TEST OK [0.011 secs, 5468 KB] Test 5: TEST OK [0.014 secs, 5468 KB] Test 6: TEST OK [0.011 secs, 5468 KB] Test 7: TEST OK [0.027 secs, 5468 KB] Test 8: TEST OK [0.057 secs, 5468 KB]All tests OK.Your program (‘fence‘) produced all correct answers! This is your submission #6 for this problem. Congratulations!Here are the test data inputs:------- test 1 ----31 22 33 1------- test 2 ----110 20------- test 3 ----91 22 33 44 24 52 55 65 74 6------- test 4 ----152 99 79 55 1010 11 77 107 33 44 55 33 66 54 105 2------- test 5 ----10011 1518 2124 3539 531 2929 3636 3939 1515 2323 1111 2424 1818 3636 2424 2828 4040 3333 1313 2828 3838 3737 55 1919 3535 4040 3434 1010 1818 3939 2929 2222 1616 2727 1212 66 1616 88 55 3030 1515 1313 77 1111 3737 3535 1111 3030 77 3838 2727 33 537 22 3939 66 2020 3737 3434 11 1212 2121 1313 1717 3636 2121 2525 1111 3636 3838 1717 77 3511 1717 2418 1515 1010 2020 1717 1515 1616 1919 1313 2222 3838 99 1539 2136 1212 3737 3131 3232 1818 1616 22 1414 1919 2020 88 3030 31------- test 6 ----832 12 11 21 22 12 11 21 22 12 11 21 22 12 11 21 22 12 11 21 22 12 11 21 22 12 11 21 22 12 11 21 22 12 11 21 22 12 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 21 21 22 11 2------- test 7 ----5001 1722 2013 2953 425 2205 316 1586 2887 918 1998 2279 7210 10310 27611 16712 313 18014 13914 23715 11416 10916 27116 29019 21720 13720 19821 24621 26222 21123 3323 7924 14024 24526 3826 6527 12327 6528 8729 21830 13630 20231 20231 6832 10232 13033 11033 11233 11633 9634 17635 15635 27838 5440 15040 25040 8441 19941 27141 5242 13143 10344 11844 21845 2646 23446 4848 23549 11349 27250 26251 11752 6253 12854 27555 13858 2058 25959 11760 17460 6160 8961 19562 26662 3065 22365 28265 7068 12068 12268 19169 12969 21370 25371 10771 6572 12872 23672 24272 27572 9273 11873 17474 20775 17675 3377 17277 25078 11478 17479 18580 14081 982 26683 2284 12284 20384 9786 2387 11788 16089 25089 27889 3590 3391 10891 15891 23292 16092 17592 5092 9894 13695 18995 8496 4196 7396 897 18797 23197 2798 19398 9299 15899 18199 22799 24999 92100 145100 16100 167100 51100 55101 230102 11102 163102 175102 220102 99103 10103 124103 224103 40104 24105 108105 95107 102107 252107 283108 100108 181108 198108 60109 287110 83112 44113 16113 41114 160114 237114 46114 72114 99115 208115 89116 12116 161117 142117 187117 239117 257118 194118 284118 60119 159119 95120 134121 75122 166122 167123 270123 90124 272125 21125 279127 128127 99128 194128 256128 28128 99129 227129 271129 295129 40130 142131 276131 32131 97133 102134 170136 164136 217136 6136 72137 183138 235139 114139 275140 23140 275142 115142 159142 274142 298143 232143 271144 35145 259147 149149 224149 227150 266155 116156 273156 71157 14158 103158 186158 2158 264158 284159 185159 276160 142160 218160 219160 222161 178161 268163 149163 216163 220164 189164 19165 157165 58166 143166 155166 160166 254166 43167 223167 239167 279167 296168 102168 104168 3169 228170 185170 219172 119172 275172 32173 125174 129174 165174 270175 100175 114175 208175 250175 34176 296176 96177 268178 131179 215180 14180 283181 125181 268182 232183 49185 167185 190185 277186 15186 199186 230186 287186 33187 147187 298187 5189 175189 215190 58191 92193 100193 166193 91194 233194 249194 69194 8195 89198 136198 168198 202199 286199 49199 91200 103200 115200 29201 168201 254202 105202 121202 205202 59202 68203 21205 156207 129207 88208 6208 77211 13213 194215 166215 251216 41216 78217 129217 201218 226218 279218 69219 10219 257219 291220 226220 262220 78222 202223 108223 193224 127224 186224 284225 173225 82226 254226 30227 119227 169227 179227 200228 72230 158230 158230 165230 166230 255231 136231 46232 102232 161232 200233 272234 71235 230235 77236 44237 163237 168239 164239 94241 62242 139243 294245 264245 81246 299249 186249 225250 108250 294250 31250 80251 5252 107253 113254 27254 73254 75255 72256 105256 133256 231257 20257 245259 100259 97260 198262 117262 7262 84264 1264 280264 53266 166266 177266 224266 26266 277268 256268 287268 45269 187269 225270 186270 230271 243271 260271 280271 96272 219272 86272 99273 269274 123275 118275 16275 207275 40275 68276 138276 142276 266277 143277 300278 107278 264279 163279 194279 266279 74280 175280 241282 186282 256283 24283 98284 114284 202284 279286 182287 144287 170287 282288 294290 101290 131290 230291 172294 128294 193294 290295 127295 60296 100296 200298 180298 299299 175299 290300 216------- test 8 ----10241 2281 2381 4151 4732 1062 1123 2053 3784 3434 4114 505 3666 1767 4648 2289 6910 18911 5912 26412 27812 36412 40912 6112 6913 12213 46714 11914 19714 23014 6915 42415 43816 38618 29118 35318 4619 1319 15020 12820 15520 35120 41220 44020 47920 48021 31021 43021 5822 33923 8624 18924 22325 40826 10226 26227 16827 30727 40527 47228 28828 35328 42430 17230 26430 33331 33132 7433 28433 39934 19634 36134 435 23435 3435 8836 15236 28137 10137 18137 27937 41238 3438 43940 14940 25340 27140 29740 34941 16841 26542 24442 35642 44643 11544 12044 12844 37444 49745 19245 47346 11046 25546 28446 45247 2547 41948 16648 39848 44248 49549 29549 40949 42650 2450 7351 12651 38051 41352 27252 44954 31656 30656 39956 41656 48656 49356 8458 13658 25558 41159 17059 7260 15860 4961 36161 9563 10763 16863 44563 49464 38764 5165 19566 21066 21666 24267 31469 10869 27269 570 14470 2871 24871 9972 21072 43573 16373 273 7174 1274 19374 23674 27074 9676 19876 23276 2877 25377 30281 1282 13782 24382 38582 43683 2283 22384 16084 19984 30084 34484 45484 5685 32985 47886 1486 35986 44787 30387 34487 36888 188 16188 17388 27588 34888 41889 189 24289 47589 47790 16091 8792 34994 40495 34096 3796 49597 30297 36997 46198 23099 10899 2099 360100 140100 335100 361101 196101 282101 384102 132103 146103 153103 396103 45104 398104 494105 9106 167106 211106 336106 439106 449107 333107 70108 158108 72108 74109 132109 267110 124110 237110 379110 96111 141111 343112 127112 138113 199114 341114 367115 258115 445116 13116 499117 43118 145118 154118 365119 126119 324119 348119 430119 89120 307122 117122 3123 126124 149124 172125 81126 109126 20126 398127 220127 306127 405127 458128 321128 35128 401129 3130 330130 51131 223131 373132 159132 266132 303132 388132 46133 346133 494135 104135 427136 352137 284137 471138 218138 83139 492140 12140 187140 228140 238141 4141 41141 89142 497143 71144 241144 383144 396144 397144 409144 87145 164145 284145 317145 458146 209146 218148 156148 175149 183149 199149 302149 375150 116151 231152 495153 227153 66154 352155 12155 127155 14156 454156 463156 483157 119158 100158 298158 60158 88159 190159 254159 322159 419160 302160 429161 375162 178163 304163 372164 139164 302166 475167 221167 293168 197168 218168 48168 85168 92169 346170 210170 88172 304172 452173 241174 18174 304174 444175 177175 20175 48176 320177 21177 63178 484178 489179 207180 88181 31181 416182 254182 377183 135185 276185 442186 290187 40188 145188 322188 354188 479189 369189 465190 188190 494192 333192 351192 402192 58193 137193 140193 155194 63195 401195 448196 119196 168196 82197 204197 241198 144198 73199 228199 377199 434199 44201 101201 481202 492203 425204 14204 86205 141205 255205 472206 303207 106207 158207 449208 159209 205210 227210 257210 272210 340210 463211 108211 109211 140211 389211 54213 19214 245214 61215 273215 40216 411218 14218 227218 23218 294218 412218 51219 18219 383220 471220 56221 148221 291221 488222 329223 106223 293223 32223 357223 77226 500226 65227 206227 242227 301228 103228 188228 242228 421229 389229 56230 110230 162230 377231 127232 289232 431232 448233 353233 42233 442233 451234 188234 20235 114236 192237 221238 274238 481239 181240 312240 484241 240241 360241 383241 412241 44242 15242 179242 387242 443242 459242 85243 233244 37245 396246 442247 2248 500251 111251 463252 138252 174252 83253 168253 432253 494254 251254 305254 409254 74255 149255 186255 297255 84257 222257 329257 414258 255258 345258 359258 410258 84259 276260 169261 226261 303261 46262 153263 406264 452264 463264 48265 440265 459266 118266 211267 453267 84268 144268 392270 404270 471271 100271 36272 210272 229272 389272 90273 411274 129274 174274 316275 100275 12276 201276 293278 232279 18279 399279 427281 449282 452284 382284 40284 445284 82285 239285 36286 372288 201289 286289 365290 205290 496291 35291 470293 141293 261293 331293 66294 185294 335295 127295 266295 44295 88296 218297 279297 47297 63298 241300 110300 30300 308300 332301 402302 155302 177302 261302 415302 97303 145303 174303 219303 332303 429304 223304 252304 33304 378305 397305 8305 84306 123306 26306 354306 52307 274307 352307 409308 16308 295309 119310 28310 329311 377312 438313 315313 89314 45315 193315 21315 367315 427315 498316 258316 373316 406317 221318 118318 412320 49321 332322 421322 476323 56324 279324 323326 20326 360327 50329 10329 104329 157329 285329 304329 313330 347331 116331 366332 210332 27332 473333 164333 24333 346335 265335 400336 295338 20339 358340 424340 458341 499343 252343 344344 380344 46344 6345 215346 211346 258346 99347 367347 38348 272348 374348 375349 461349 74349 88351 233351 410352 131352 258352 268353 131353 198353 37353 457354 122354 144354 91356 40356 60357 497358 33359 410359 7360 270360 30360 34361 156361 379361 414362 401363 89364 252364 487365 158365 447366 199366 306367 118367 178367 261368 125369 11369 151369 213369 274369 433369 447372 114372 130372 246372 476373 326373 425374 193374 229375 300375 315375 408377 192377 211377 27377 316378 247378 26379 185379 369380 369380 398380 41382 242382 271383 315383 380383 47383 82384 196385 140386 405387 285387 461388 97389 106389 113389 42389 447391 119391 94392 74393 447396 313396 362396 56397 309397 42398 111398 259398 30398 318398 456399 130399 20399 218400 115401 132401 163401 254401 349402 128402 21403 59404 144404 27404 305405 315405 413405 477406 440406 451408 148408 423408 450409 143409 204409 208409 426409 463409 485410 103410 453410 86411 195411 257411 300411 416411 449412 194412 207412 382412 393412 49412 84413 268413 308413 76414 411414 482415 403415 48415 66416 211416 264416 461417 356418 1418 146418 398419 12419 353420 289421 219421 327422 234423 4424 167424 338424 372424 446425 235425 445426 412426 429427 15427 258427 415429 159429 190429 35429 372430 315430 480430 82431 290432 215433 159433 435434 223435 267435 294436 391438 389438 76439 226439 300439 433440 135440 260440 363440 404442 354442 391442 418442 426443 182444 58445 263445 347445 424445 430446 101446 182447 132447 241447 324447 40447 456447 98448 142448 233448 483449 242449 297449 369449 409449 70450 207451 439451 456452 257452 293452 348452 364452 64453 306453 408453 63454 474454 99456 149456 251456 295457 453458 124458 220458 447459 1459 310461 132461 329461 37461 420463 175463 188463 203463 253463 77464 105465 369467 27470 296471 106471 156471 56472 413472 73473 180473 87473 97474 230474 452475 232475 448475 64476 303476 326477 214477 44478 110479 144479 498480 112480 202481 107481 307482 240483 19483 418484 275484 311485 192486 474487 305488 214489 170489 175492 38492 52493 254494 218494 318494 329494 417494 440495 133495 145495 67496 383497 103497 422497 475498 133498 401499 489499 76500 103500 233Keep up the good work!Thanks for your submission!
usaco-3.3-fence-pass
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。