ZOJ 2332 Gems (最大流构图)

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;

}