ZOJ 2332ネットの流れの英語の読解問題

テーマ:
ある人はたくさんの宝石を持っていて、いろいろな色と形を持っていて、その人は超能力を持って宝石を変えることができて、1種の色と形を変えることができます.この人は彼女に宝石をあげます.彼が我慢している形の宝石には上限があり、彼女が我慢している色の宝石には上限があります.あの人に宝石を彼女にあげて、二人とも満足させることができますか?
考え方:
もともと私の考えは間違っていた.次の最初のコードのように書きます.
BFはまず自分にできるだけ同じ形の宝石を我慢させて、それから我慢できないものを彼女に流して、自分がいっぱいになることができる时、つまり自分が完全に我慢することができて、彼女は自分が我慢できない宝石をすべて吸収することができて、このように1つの条件に合っています.しかし、私のこの考え方は間違っています.なぜなら、また最初に流れたとき、BFは宝石を変えることができて、彼女にできるだけ受け入れることができて、私の考えの中でこの一歩がなくて、直接彼を彼女に流しました.
実はテーマはこうすることができます.
宝石の山、BFとGF、BF、GFに分けて、すべて我慢の限界があって、つまり容量.宝石が分けられるようになったとき、Yesではないでしょうか.そう思うと、構図が出てきて、1 Y.

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstdlib>
#define MN 230
#define INF 0x00FFFFFF
#define CC(what) memset( what,0,sizeof(what) )
#define FF(i,M) for( int i=0;i<M;i++ )
template<class T> void inline checkmin( T&a,T b ){ if( a>b||a==-1 ) a=b; }
using namespace std;

int R,C,s,t;
int m[11][11],maze[MN][MN];
int cntR[11],cntC[11],limR[11],limC[11];
void setG()
{
     int r1,c1,r2,c2,u,v,k;
     CC(cntR),CC(cntC),CC(maze),CC(limR),CC(limC);
     scanf( "%d%d",&R,&C );
     FF(i,R)FF(j,C){
          scanf( "%d",&m[i][j] );
          cntR[i]+=m[i][j];
          cntC[j]+=m[i][j];
     }
     scanf( "%d",&k );
     FF(i,k){
          scanf( "%d%d%d%d",&r1,&c1,&r2,&c2 );
          u=R+C+1+r1*C+c1;
          v=R+C+1+r2*C+c2;
          maze[u][v]=maze[v][u]=INF;
     }
     FF(i,R) scanf( "%d",&limR[i] );
     FF(i,C) scanf( "%d",&limC[i] );
     s=0;t=R+C+R*C+1;
     FF(i,R)
	 if( cntR[i]-limR[i]>0 )
	 	 maze[s][i+1]=cntR[i]-limR[i];
     FF(i,C) maze[R+1+i][t]=limC[i];
     FF(i,R) FF(j,C){
             v=R+C+1+i*C+j;
             maze[i+1][v]=INF;
             maze[v][R+j+1]=INF;
     }
}

int cur[MN],pre[MN],dis[MN],gap[MN];
int sap()
{
    CC(cur),CC(dis),CC(gap);
    int u=pre[s]=s,maxflow=0,aug=-1;
    gap[0]=t+1;
    while( dis[s]<=t ){
loop:
           for( int v=cur[u];v<=t;v++ )
           if( maze[u][v]&&dis[u]==dis[v]+1 )
           {
               cur[u]=v;
               checkmin( aug,maze[u][v] );
               pre[v]=u;
               u=v;
               if( v==t )
               {
                   maxflow+=aug;
                   for( u=pre[u];v!=s;v=u,u=pre[u] )
                   {
                        maze[u][v]-=aug;
                        maze[v][u]+=aug;
                   }
                   aug=-1;
               }
               goto loop;
           }
           int mind=t;
           for( int v=0;v<=t;v++ )
           if( maze[u][v]&&mind>dis[v] )
           {
               cur[u]=v;
               mind=dis[v];
           }
           if( --gap[dis[u]]==0 )break;
           gap[dis[u]=mind+1]++;
           u=pre[u]; 
    }
    return maxflow;
}


bool work()
{
     int KK=0;
     FF(i,R)
	 if( cntR[i]-limR[i]>0 )
	 	 KK+=cntR[i]-limR[i];
     if( KK==sap() ) return true;
     else return false;
}


int main()
{
    int T;
    scanf( "%d",&T );
    while( T-- )
    {
           setG();
           if( work() ) printf( "Yes
" );
           else printf( "No
" );
           //getchar();
    }
    return 0;
} 

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstdlib>
#define MN 230
#define INF 0x00FFFFFF
#define CC(what) memset( what,0,sizeof(what) )
#define FF(i,M) for( int i=0;i<M;i++ )
template<class T> void inline checkmin( T&a,T b ){ if( a>b||a==-1 ) a=b; }
using namespace std;

int R,C,s,t,total;
int m[11][11],maze[MN][MN];
int cntR[11],cntC[11],limR[11],limC[11];
void setG()
{
     int r1,c1,r2,c2,u,v,k;
     CC(maze);
     scanf( "%d%d",&R,&C );
	 s=0;t=R+C+R*C+3;
	 int BF=R+C+R*C+1,GF=R+C+R*C+2;
	 total=0;
     FF(i,R)FF(j,C){
          u=R+C+1+i*C+j;
          scanf( "%d",&maze[s][u] );
          total+=maze[s][u];
          //cntR[i]+=m[i][j];
          //cntC[j]+=m[i][j];
     }
     scanf( "%d",&k );
     FF(i,k){
          scanf( "%d%d%d%d",&r1,&c1,&r2,&c2 );
          u=R+C+1+r1*C+c1;
          v=R+C+1+r2*C+c2;
          maze[u][v]=maze[v][u]=INF;
     }
     FF(i,R) scanf( "%d",&maze[i+1][BF] );
     FF(i,C) scanf( "%d",&maze[R+i+1][GF] );
     FF(i,R) FF(j,C){
             v=R+C+1+i*C+j;
             maze[v][i+1]=INF;
             maze[v][R+j+1]=INF;
     }
     maze[BF][t]=maze[GF][t]=INF;
}

int cur[MN],pre[MN],dis[MN],gap[MN];
int sap()
{
    CC(cur),CC(dis),CC(gap);
    int u=pre[s]=s,maxflow=0,aug=-1;
    gap[0]=t+1;
    while( dis[s]<=t ){
loop:
           for( int v=cur[u];v<=t;v++ )
           if( maze[u][v]&&dis[u]==dis[v]+1 )
           {
               cur[u]=v;
               checkmin( aug,maze[u][v] );
               pre[v]=u;
               u=v;
               if( v==t )
               {
                   maxflow+=aug;
                   for( u=pre[u];v!=s;v=u,u=pre[u] )
                   {
                        maze[u][v]-=aug;
                        maze[v][u]+=aug;
                   }
                   aug=-1;
               }
               goto loop;
           }
           int mind=t;
           for( int v=0;v<=t;v++ )
           if( maze[u][v]&&mind>dis[v] )
           {
               cur[u]=v;
               mind=dis[v];
           }
           if( --gap[dis[u]]==0 )break;
           gap[dis[u]=mind+1]++;
           u=pre[u]; 
    }
    return maxflow;
}


bool work()
{
     if( total==sap() ) return true;
     else return false;
}


int main()
{
    int T;
    scanf( "%d",&T );
    while( T-- )
    {
           setG();
           if( work() ) printf( "Yes
" );
           else printf( "No
" );
           //getchar();
    }
    return 0;
}