ZOJ 2332 Gems (最大流构图)

于 2011年08月15日 发布在 算法&&ACM 跳到评论

ZOJ 2332 Gems

alsomagic 想给女朋友送宝石,但是gf不希望某种颜色太多,alsomagic 也不希望留在手中的宝石某种形状的太多(这个在刚开始看题时候理解不清楚,哎),还好alsomagic 有超能力,能让A形状B颜色的转换成C形状D颜色的,问能不能产生合适的分配。

 

头文件和模板参见我的图论模板。。。

Network< 200, 200000 > Net;
int N,M,D;

int main(void){
    int S,T,H,L,i,j,k,from,to,w;
    int cases,total = 0;;
    scanf("%d",&cases);
    while( cases-- ){
        scanf("%d%d",&N,&M);
        Net.init( N*M+M+N+4 );

        H = N*M+N+M;
        L = H+1;
        S = L+1;
        T = S+1;

        total = 0;
        for( i = 0; i < N; i++ )
            for( j = 0; j < M; j++ ){
                scanf("%d",&w);
                total += w;
                Net.add( S, i*M+j, w );
                Net.add( i*M+j, N*M+i, INF);
                Net.add( i*M+j, N*M+N+j, INF );
            }

        scanf("%d",&D);
        while( D-- ){
            scanf("%d%d",&i,&j);
            from = i*M+j;
            scanf("%d%d",&i,&j);
            to   = i*M+j;
            Net.add( from, to, INF );
            Net.add( to, from, INF );
        }
        for( i= 0; i < N; i++ ){
            scanf("%d",&w);
            Net.add( N*M+i, H, w );
        }
        for( i = 0; i < M ; i++ ){
            scanf("%d",&w);
            Net.add( N*M+N+i, L,w );
        }
        Net.add( H, T, INF );
        Net.add( L, T, INF );
        i = Net.MaxFlowDinic(S,T);
        //cout << i << '&' <<endl;
        if( total ==i )
            puts("Yes");
        else puts("No");
    }
    return 0;

}

本文共有 14条评论 | 沙发:文章评论

  1. 小媛说道:

    哇~~~~~~~~~~~姐~~~~~~~这题貌似我以前看过也~~~~~~~~但是不会做也~~~~~~~

  2. acmol说道:

    路过。。看到是最大流忍不住踩下。。

  3. Snow_storm说道:

    But each way of transform can only be used ONCE! 难道我理解错这句了???!!!! 我忍不住吐槽这题阿

  4. xcy_DDV说道:

    弱问一下,zoj的题目里面那么多乱码,怎么读题啊

  5. xcy_DDV说道:

    你就是传说中的“党姐”??Orz

  6. xcy_DDV说道:

    好囧……那道题我也试了,内存死活刷不进200k啊 :cry:

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)