Algoogle

Algorithm for Programming Contest

PA 2006 Travel Agency

Category: PA Tag: max-flow

Travel Agency

問題概要


n人の客がいる.
この人達に旅行を手配するとそれぞれの利益をもたらす(負もある).
またこれらの人はそれぞれ人と関係があり, が旅行に行かない場合の不利益を出す.
利益を最大にするような客の選び方を求めよ

解法


この問題はテストケースをダウンロードして, テストケース番号に応じて埋め込んだ答えを吐くコードを提出しなければならないことに注意すること.
コードはそのとき使ったコード全てを載せておく.

  • 説明抜きの解法

もたらす利益が非負であるものの総和が利益の上限.
ここから減る利益を最小化したい.
頂点sから利益が非負の客に利益をコストとする有向辺を張る.
利益が負の客から頂点tに利益の絶対値をコストとする有向辺を張る.
次に客iと関係があるをコストとする有向辺を張る.
構築したグラフのS-T最小カットが減る利益の最小値, 集合Sが選ぶ客の集合, 集合Tを選ばない客の集合となる.

最小カットは最大流を求めればよく, 最大流を求めた後に集合Sはsから容量が正の辺を辿っていける頂点が選ぶ客になる.

  • なぜうまくいくのか

頂点sから伸びてるのは増える分だけ, また増える分は全て頂点sから伸びてる.
つまりsから伸びてる辺をカットするとその先の頂点をTに入れるということなので利益がその分減る.
頂点tに入る辺は不利益をもたらす客からの辺で, 不利益をもたらす客からの辺は全てtに伸びてる.
この辺をカットするということはその客をSに入れるということなのでその利益がその分減る.
その他の辺は利益が減る辺で, その辺をカットするということは前の頂点はSに, 後の頂点はTに含まれるということ.
これはまさに問題の客同士の関係を表している.

どの辺を切っても利益が減ることを表していて, 頂点を2つの集合に分けるような最小のコストを求めることになる.
つまり最小カットを求めるとよいということになる.

コード


(travel.sh) download
1
touch _travel.cpp; for F in biu*.in; do ./a.out < $F >> _travel.cpp; done;
(travel.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000;

inline void chmin(int &a, int b) { a = min(a,b);}

int n, m, sz[1<<12];
vector<int> g[1<<12], dp[1<<12];

int dfs(int v, int p)
{
        dp[v].assign(2,0);
        sz[v] = 1;
        for (int i = 0; i < (int)g[v].size(); i++) {
                if(g[v][i] == p) continue;
                sz[v] += dfs(g[v][i],v);
                dp[v].resize(sz[v]+1,inf);
                dp[n].assign(sz[v]+1,inf);
                for (int j = 1; j <= sz[v]; j++) {
                        chmin(dp[n][j],dp[v][j]+1);
                        for (int a = 1; a < j; a++)
                                if(sz[g[v][i]] >= j-a)
                                        chmin(dp[n][j], dp[v][a]+dp[g[v][i]][j-a]);
                }
                swap(dp[v],dp[n]);
        }
        return sz[v];
}

void solve()
{
        dfs(0,-1);
        int k;
        while(m--) {
                scanf("%d", &k);
                int ans = dp[0][k];
                for (int i = 1; i < n; i++)
                        if(sz[i] >= k) chmin(ans, dp[i][k]+1);
                printf("%d\n", ans);
        }
}

void input()
{
        scanf("%d", &n);
        int u, v;
        for (int i = 0; i < n-1; i++) {
                scanf("%d%d", &u, &v); u--; v--;
                g[u].push_back(v);
                g[v].push_back(u);
        }
        scanf("%d", &m);
}

int main()
{
        input();
        solve();
        return 0;
}
(travel2.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
using namespace std;
int k;
int main() {
scanf("%d",&k);
if(k == 0) printf("3\n1 2 4\n");
if(k == 1) printf("4\n1 3 4 5\n");
if(k == 10) printf("329\n1 2 5 6 17 22 26 27 29 32 34 35 37 40 49 50 53 54 57 58 60 63 66 69 73 74 78 81 82 89 91 95 96 97 99 100 101 107 110 111 119 120 123 126 127 131 135 136 137 138 139 143 144 147 148 151 152 153 155 157 158 159 163 168 169 172 175 183 186 188 192 196 200 205 206 211 213 223 227 228 231 234 236 238 244 246 247 253 256 257 258 259 260 266 268 269 271 276 277 278 287 289 290 291 293 295 297 299 300 302 306 311 313 315 317 325 326 328 339 345 353 357 359 363 367 370 371 379 382 383 384 386 388 390 391 392 393 394 401 404 405 406 407 408 409 411 418 419 420 421 423 427 431 434 438 445 446 449 452 457 460 464 467 468 470 474 475 476 477 481 484 486 487 492 494 496 510 513 516 521 524 528 529 532 537 540 541 544 545 549 550 554 557 559 560 562 567 568 571 573 575 577 578 585 586 590 593 599 610 612 613 615 618 619 630 636 640 642 644 645 646 647 656 657 660 661 669 670 673 675 677 680 681 682 683 689 695 700 704 706 707 712 714 715 716 717 719 720 724 725 728 731 734 735 736 739 741 744 745 747 748 753 756 757 760 761 763 764 766 770 777 782 783 785 788 789 795 800 809 811 824 831 835 838 843 847 851 856 860 862 868 869 872 873 874 875 878 879 884 885 888 892 895 901 902 905 908 911 919 924 928 929 936 937 941 945 948 955 959 967 969 972 977 981 986 991 997 998 1000\n");
if(k == 2) printf("0\n");
if(k == 3) printf("12\n2 3 6 7 8 11 14 15 16 17 22 25\n");
if(k == 4) printf("48\n1 2 3 4 5 6 11 12 15 17 19 21 23 24 25 27 29 31 32 33 35 38 40 41 42 43 44 45 46 49 51 52 53 54 55 57 58 59 61 62 65 66 67 68 69 72 74 75\n");
if(k == 5) printf("75\n1 2 4 5 10 11 12 14 15 16 17 19 26 27 28 30 33 36 37 39 41 42 44 45 46 47 48 53 56 57 58 60 61 62 66 70 72 73 75 76 78 82 85 87 89 90 91 94 95 99 100 103 104 105 109 111 112 114 117 119 124 126 128 130 131 133 136 139 141 142 143 145 146 148 149\n");
if(k == 6) printf("112\n3 4 5 8 9 11 13 14 17 21 24 26 28 32 33 34 41 44 45 51 52 57 58 60 63 64 67 68 70 74 75 76 77 79 83 84 87 88 91 92 93 95 96 98 99 104 105 106 107 109 112 116 118 119 120 121 122 124 126 127 128 129 130 132 133 136 137 139 140 143 144 145 148 151 153 157 159 160 161 164 165 170 171 172 173 174 175 176 177 180 181 182 185 187 188 189 191 192 193 195 197 198 199 200 203 205 207 210 211 213 220 225\n");
if(k == 7) printf("595\n1 2 3 4 6 10 11 12 17 18 21 22 23 28 29 30 31 32 33 34 37 38 40 41 42 43 44 45 47 49 51 52 53 57 58 60 61 62 64 65 66 68 71 72 73 76 78 82 83 84 85 87 90 91 92 93 94 96 100 101 102 103 106 108 109 110 111 114 115 116 117 118 119 121 123 124 127 130 131 132 133 134 135 137 142 143 144 145 147 148 149 151 153 154 155 156 158 161 163 165 166 169 170 171 172 174 175 176 178 180 184 185 186 187 188 189 190 191 193 195 196 197 199 201 203 205 208 209 212 213 215 217 218 219 220 222 224 225 229 232 235 237 238 241 243 244 246 247 248 254 256 258 259 262 263 264 265 267 268 270 271 275 276 277 278 279 280 281 282 284 285 286 287 290 292 294 296 297 298 299 301 302 303 304 306 308 312 313 315 323 324 325 326 328 329 330 331 332 333 334 336 337 338 339 341 344 345 346 347 348 349 350 351 354 355 356 358 359 360 361 363 365 366 367 368 370 371 372 373 375 376 380 383 385 387 388 389 391 392 394 397 399 402 404 406 407 409 412 413 414 416 417 418 420 423 427 429 430 432 433 434 435 437 439 440 441 443 444 445 447 449 450 452 453 454 456 458 459 460 461 463 464 468 469 470 475 476 477 480 482 483 484 485 487 488 489 495 496 497 498 500 501 502 503 504 507 508 510 512 515 516 518 521 523 524 526 528 529 530 531 534 538 542 544 545 547 548 549 552 557 559 561 563 564 566 567 571 572 573 576 577 581 583 584 586 589 591 592 593 597 599 600 601 602 603 604 610 611 614 615 616 618 620 621 622 623 624 625 626 627 628 629 631 632 633 635 636 637 638 639 640 641 642 643 644 645 647 648 649 650 652 653 655 656 658 659 660 661 662 663 664 665 666 667 669 671 673 676 678 680 681 682 683 684 686 687 688 689 690 691 692 693 697 700 702 703 707 710 711 712 713 714 715 716 718 719 720 725 726 728 732 733 735 736 737 738 740 741 742 745 747 750 754 758 759 760 762 763 766 767 768 770 771 772 776 777 779 784 785 786 787 788 790 791 794 796 799 800 801 802 803 804 806 807 808 809 812 814 817 818 819 820 821 823 824 826 828 830 831 832 833 834 835 837 840 841 842 845 846 847 850 851 852 853 855 856 857 859 861 862 868 871 872 874 875 876 877 878 880 883 884 886 887 888 890 891 893 895 896 899 900 903 905 908 911 912 915 917 919 920 921 927 930 931 932 935 936 937 938 940 943 945 946 947 948 953 955 956 957 958 960 962 963 964 966 968 969 971 972 973 976 977 978 981 983 984 988 989 990 991 993 994 995 997 999\n");
if(k == 8) printf("672\n2 3 5 6 7 8 10 12 14 16 17 18 19 21 24 25 26 27 28 32 33 34 36 37 39 40 41 42 43 44 45 47 49 50 52 53 54 55 56 59 60 61 62 63 65 66 70 71 72 74 75 76 77 78 80 81 82 83 84 85 86 87 88 89 91 92 93 94 95 96 97 98 99 101 102 104 105 106 107 110 113 116 118 121 122 123 124 127 130 131 132 134 135 136 137 142 149 150 151 152 153 156 157 159 160 161 162 163 166 168 169 172 175 178 180 181 183 184 185 188 189 191 192 193 194 196 197 198 199 200 201 202 204 206 207 208 209 210 211 212 213 214 215 216 219 220 221 222 223 224 226 228 230 231 232 233 235 236 238 239 242 243 244 245 246 249 250 252 253 254 255 258 260 262 263 265 266 267 268 272 273 274 275 276 279 280 282 283 284 285 286 287 288 289 290 291 294 295 297 300 303 304 305 307 308 309 312 313 314 315 316 317 319 321 322 324 325 327 328 329 332 333 334 335 336 338 339 340 341 342 343 344 345 346 347 348 350 351 352 353 357 358 361 362 364 366 368 369 370 372 373 374 375 376 377 379 381 382 383 384 387 389 390 391 392 393 395 396 397 399 400 403 404 408 409 410 411 412 413 414 418 420 421 422 424 425 426 427 428 429 430 435 436 438 439 440 441 442 443 444 445 446 447 448 450 453 454 455 456 458 459 460 461 464 465 466 467 468 470 471 472 473 474 475 476 478 480 484 485 487 488 489 490 491 492 495 496 498 500 501 503 505 506 507 508 511 512 513 517 518 520 521 522 523 525 526 527 528 529 531 532 534 535 539 541 542 545 546 547 550 551 552 555 558 559 560 561 562 565 566 567 568 569 570 571 573 576 578 580 582 583 584 589 592 593 595 596 597 598 602 604 605 606 607 608 609 610 611 612 613 614 617 619 620 621 622 623 626 627 628 629 630 632 634 635 636 637 639 641 642 643 644 645 646 647 648 650 651 652 653 655 656 657 659 661 662 663 665 669 671 672 673 674 675 676 677 678 679 681 682 683 684 685 686 687 688 691 692 693 697 698 699 700 701 702 703 704 707 708 710 712 713 715 716 717 718 720 722 725 726 727 728 729 730 734 737 738 739 742 743 745 747 749 750 751 752 753 755 756 757 760 761 762 763 766 767 770 773 774 775 776 777 778 779 781 783 784 785 786 787 788 789 790 792 793 794 797 800 802 804 805 806 809 811 813 814 815 816 817 818 819 821 822 823 825 828 829 830 831 834 835 836 838 839 840 842 844 845 846 847 848 850 852 855 857 858 859 860 861 862 863 864 868 869 870 872 873 875 877 879 881 883 884 886 888 889 892 893 894 895 896 897 898 900 902 905 906 907 908 909 910 911 913 915 917 919 920 924 925 928 929 930 931 932 933 934 935 936 938 939 940 941 943 944 945 946 947 948 949 953 955 956 957 960 963 964 965 966 967 968 971 972 973 974 975 976 978 979 981 982 984 986 987 988 990 991 992 993 995 996 997 999\n");
if(k == 9) printf("653\n2 3 6 7 11 12 13 15 16 18 19 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 37 44 45 46 47 48 49 50 51 52 55 56 59 60 61 63 64 65 66 68 69 70 72 73 74 77 79 80 84 85 88 89 90 92 93 94 102 103 104 106 109 110 111 112 114 115 117 118 121 122 123 126 128 129 130 131 132 133 134 137 138 139 140 141 142 146 147 150 151 152 155 156 158 162 163 165 166 167 172 173 175 176 177 180 181 182 184 186 187 191 192 193 194 195 196 198 199 200 201 203 205 206 208 210 212 213 215 216 217 220 221 222 223 226 228 229 232 233 234 236 239 240 241 244 245 247 250 254 255 256 257 258 260 261 262 263 265 266 268 269 270 271 272 273 274 275 276 277 278 279 280 282 283 284 285 287 288 289 290 293 294 295 296 297 298 299 300 302 303 304 305 306 307 308 310 311 315 316 318 319 323 325 326 327 328 330 332 333 334 336 337 338 339 340 341 342 345 346 347 349 350 351 352 353 354 355 356 360 361 363 365 366 369 370 372 374 375 376 377 378 379 380 381 382 384 386 387 388 389 391 392 393 394 395 398 399 400 402 403 404 405 408 409 410 411 412 414 415 416 419 421 422 423 424 425 426 429 432 433 434 435 436 438 439 440 441 442 443 445 446 449 451 453 454 455 456 457 458 459 460 463 466 468 471 472 473 474 475 476 477 478 479 480 481 482 485 486 487 488 489 491 492 493 495 498 499 500 501 502 503 504 505 506 507 508 509 513 516 517 519 520 521 523 525 526 528 530 532 538 539 542 544 545 548 549 550 551 554 555 556 558 559 560 561 564 568 570 571 574 575 576 577 578 579 580 581 582 585 586 587 592 593 594 596 598 599 601 602 604 606 607 608 609 610 612 613 615 618 622 625 627 630 631 632 633 634 635 637 638 639 641 642 645 646 647 648 649 651 652 653 654 656 658 659 660 661 662 665 666 668 669 671 673 674 676 677 678 679 680 681 682 684 685 686 687 688 689 690 691 693 695 697 698 700 702 703 704 705 707 711 712 713 714 718 719 720 721 722 723 724 725 727 729 730 732 733 734 739 740 741 743 744 745 746 748 750 751 752 754 755 756 758 759 761 762 763 765 766 767 768 771 772 774 776 777 778 779 780 781 784 786 788 789 790 792 793 794 795 796 797 798 799 801 802 803 804 806 808 809 810 811 812 813 814 815 818 819 822 824 826 828 830 831 833 834 835 837 838 839 840 842 844 845 846 847 849 850 852 855 856 857 859 862 863 864 868 869 870 871 873 874 877 878 880 883 884 885 886 887 889 892 896 897 898 899 900 902 903 904 905 908 911 912 913 914 916 917 921 923 924 927 929 933 934 935 936 937 938 940 941 942 948 949 950 951 952 953 954 955 956 958 959 961 963 964 965 967 970 971 972 973 975 976 977 978 979 980 981 982 983 987 988 989 992 996 997 1000\n");
return 0;
}

Comments