POJ3422 Kaka's Matrix Travels

分手后的思念是犯贱 2021-12-20 20:17 152阅读 0赞

题目：[http://poj.org/problem?id=3422][http_poj.org_problem_id_3422]

拆点：自己的两个点间一条边cap=1，w=a(点权)，表示取一遍值；另一条边cap=k-1，w=0，表示不取值而最多走k-1遍。

原图两点间cap=k，w=0。别忘了是出点连到入点。

1.为k-1或k的边权其实可以是INF，这时源点的初flow只能是k，但会错！为什么？

2.bfs（其实是spfa）里退出条件是t点的dis是不是初值。不能过程中一遇到t就return！因为是spfa，第一次遇到不一定是最优的。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int INF=1005;
    int n,m,head[5005],xnt=1,cur[5005],dis[5005];
    int pre[5005],incf[5005],ans,t,x,ct;
    bool in[5005];
    struct Edge{
        int next,to,cap,w;
        Edge(int n=0,int t=0,int c=0,int ww=0):next(n),to(t),cap(c),w(ww) {}
    }edge[20005];
    queue<int> q;
    void add(int x,int y,int c,int ww)
    {
        edge[++xnt]=Edge(head[x],y,c,ww);head[x]=xnt;
    //    printf("x=%d y=%d c=%d w=%d\n",x,y,c,ww);
        edge[++xnt]=Edge(head[y],x,0,-ww);head[y]=xnt;
    //    printf("x=%d y=%d c=%d w=%d\n",y,x,0,-ww);
    }
    bool bfs()
    {
        memset(dis,-2,sizeof dis);//
        memset(in,0,sizeof in);
        while(q.size())q.pop();
        q.push(1);dis[1]=0;in[1]=1;incf[1]=m;
        while(q.size())
        {
            int k=q.front();q.pop();in[k]=0;//
            for(int i=head[k],v;i;i=edge[i].next)
                if(dis[v=edge[i].to]<dis[k]+edge[i].w&&edge[i].cap)
                {
                    dis[v]=dis[k]+edge[i].w;
                    incf[v]=min(incf[k],edge[i].cap);
    //                if(++ct<=10)printf("v=%d incfv=%d edgecap=%d\n",v,incf[v],edge[i].cap);
                    pre[v]=i;
                    if(!in[v])in[v]=1,q.push(v);
    //                if(v==t)return true;//
                }
        }
        if(dis[t]<0)return false;/
        return true;//
    }
    void ek()
    {
    //    printf("incf=%d\n",incf[t]);
        int x=t;
        while(x!=1)
        {
            int k=pre[x];
    //        ans+=edge[k].w*incf[t];//这个也可以 
            edge[k].cap-=incf[t];
            edge[k^1].cap+=incf[t];
            x=edge[k^1].to;
        }
        ans+=dis[t]*incf[t];//
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        t=2*n*n;//
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                int k=n*(i-1)+j;
                scanf("%d",&x);
                add(k,k+n*n,1,x);add(k,k+n*n,m-1,0);
                if(i+1<=n)add(k+n*n,k+n,m,0);
                if(j+1<=n)add(k+n*n,k+1,m,0);
            }
        while(bfs())
        {
            memcpy(cur,head,sizeof head);
            ek();
        }
        printf("%d",ans);
        return 0;
    }

大数据2组：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

20 8
    851 28 749 733 797 281 380 553 820 362 913 416 997 11 821 693 200 977 392 843
    981 899 200 889 849 120 223 427 349 165 570 146 288 526 383 301 868 240 671 991
    807 572 253 962 387 862 725 276 271 990 232 393 87 494 887 314 346 222 238 589
    435 61 395 797 267 553 135 491 316 641 749 429 481 192 496 86 412 164 50 734
    688 600 922 227 528 71 141 647 831 155 528 925 466 965 301 519 562 277 997 897
    703 460 181 355 266 55 643 443 993 887 851 553 641 423 661 327 6 14 697 337
    455 582 758 937 584 172 431 607 247 833 216 199 571 488 407 874 810 193 486 921
    499 349 824 71 387 883 978 375 907 595 700 839 969 441 544 827 382 795 570 133
    529 630 528 539 146 711 44 97 969 142 304 33 512 759 610 864 782 604 120 747
    62 437 237 457 495 402 133 491 437 834 373 249 912 277 230 527 171 927 348 448
    592 709 938 522 66 677 417 355 514 481 664 977 823 517 965 272 912 106 189 447
    771 177 441 884 500 652 642 394 302 289 446 200 661 672 251 988 175 15 700 280
    336 612 674 531 917 467 20 675 772 465 706 217 626 296 246 813 996 907 340 69
    411 141 643 632 225 309 828 32 73 341 715 919 134 131 237 336 130 503 641 602
    155 894 465 945 921 551 435 821 402 860 690 943 585 875 651 337 933 869 581 413
    134 38 200 97 94 143 233 945 389 497 941 69 509 475 973 469 327 653 760 771
    854 133 319 800 898 2 53 217 496 104 677 51 792 147 993 181 230 720 32 605
    838 904 511 637 578 398 291 327 198 203 918 71 782 319 873 352 102 459 841 490
    993 37 77 563 622 828 110 387 160 741 327 796 605 533 512 641 242 984 742 214
    637 153 709 441 987 514 24 776 163 231 648 915 570 894 460 491 184 825 904 707
    
    
    154093
    
    
    
    19 10
    520 305 854 266 616 47 266 677 361 204 523 660 807 876 914 565 782 238 639
    266 956 50 797 202 169 835 78 254 770 975 678 327 871 404 348 614 201 93
    470 428 392 277 37 35 892 268 297 980 691 0 974 579 626 190 287 464 559
    465 953 56 182 722 148 723 115 392 5 423 224 802 527 333 911 355 540 442
    418 676 247 297 312 289 435 182 891 925 545 534 800 871 446 30 399 257 811
    233 844 990 481 614 972 965 789 369 20 619 440 849 583 997 426 106 222 870
    448 908 213 750 44 115 364 364 580 832 411 333 605 936 313 782 593 396 391
    246 614 809 792 511 74 600 172 303 348 905 429 306 525 35 177 34 566 815
    690 49 539 566 331 574 545 672 588 535 388 119 239 486 212 755 35 263 473
    791 857 305 301 716 981 411 408 293 791 552 746 306 723 518 972 321 622 780
    728 417 467 346 306 425 701 933 567 449 597 363 366 735 661 123 883 933 430
    25 771 392 111 257 917 556 144 386 382 863 334 622 256 747 951 798 716 560
    8 938 205 426 757 322 639 958 194 287 240 546 295 13 446 494 81 973 337
    670 135 62 42 945 473 180 83 535 80 804 681 598 818 798 272 53 837 908
    110 669 254 658 595 77 834 263 959 206 300 163 965 814 616 977 846 536 560
    711 937 251 94 227 193 986 369 681 384 300 355 218 523 61 690 583 717 949
    805 686 768 887 186 468 145 757 13 588 620 282 307 343 857 968 40 260 405
    923 558 930 539 734 104 68 316 540 774 740 917 882 705 219 488 811 809 167
    462 332 716 606 652 585 10 843 427 823 863 351 164 291 865 993 979 219 379
    
    
    158617

数据

转载于:https://www.cnblogs.com/Narh/p/8625787.html

[http_poj.org_problem_id_3422]: http://poj.org/problem?id=3422
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/f98935bdd5aa479faf7393b5ca8407c1.png