NYOJ 哭泣天使 sap求最大流

题目大意：中文题。

算法思路：因为他是网格，所以我们把将每一行看成点，将每一列看成点，将行与超级源点连接，行再与列相连接，列再与超级会点相连，求最大流即可。

#include<bits/stdc++.h>
using namespace std;
#define INF 0xfffffff
#define MAXN 600
int t;
int m,n,sum1,sum2,src,sink;
int a[MAXN],b[MAXN];
int maps[MAXN][MAXN],pre[MAXN],level[MAXN];
int gap[MAXN];

int sap(int s,int t)
{
   memset(pre,-1,sizeof(pre));
    memset(level,0,sizeof(level));
    memset(gap,0,sizeof(gap));
    gap[0]=t+1;
    int u=s,ans(0);
    while(level[s]<t+1)
    {
        int v;
        for(v=0;v<=t;v++)
        {
            if(maps[u][v]>0 && level[u]==level[v]+1)
                break;
        }
        if(v<=t)
        {
            pre[v]=u;
            u=v;
            if(v==t)
            {
                int minflow=INF;
                for(int i=v;i!=s;i=pre[i])
                    if(minflow>maps[pre[i]][i])
                        minflow=maps[pre[i]][i];
                ans+=minflow;
                for(int i=v;i!=s;i=pre[i])
                {
                    maps[pre[i]][i]-=minflow;
                    maps[i][pre[i]]+=minflow;
                }
                u=s;
            }
        }
        else
        {
            int mindis=t+10;
            for(int i=0;i<=t;i++)
            {
                if(maps[u][i]>0 && mindis>level[i]+1)
                    mindis=level[i]+1;
            }
            --gap[level[u]];
            if(gap[level[u]]==0) return ans;
            level[u]=mindis;
            gap[mindis]++;
            if(u!=s) u=pre[u];
        }
    }
    return ans;
}
int main()
{


    scanf("%d",&t);
    while(t--)
    {
        memset(maps,0,sizeof(maps));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        sum1=0;
        sum2=0;
        scanf("%d%d",&m,&n);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&a[i]);
            sum1+=a[i];
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            sum2+=b[i];
        }
        if(sum1!=sum2)
        {
             printf("Terrible\n");
             continue;
        }

            src=0;
            sink=n+m+1;
          
            for(int i=1;i<=m;i++)
            {
                maps[src][i]=a[i];
                for(int j=1;j<=n;j++)
                {
                    maps[i][j+m]=1;
                    if(i<2)
                        maps[m+j][sink]=b[j];
                }
            }


        int ans=sap(src,sink);
        if(sum1!=ans)
            printf("Terrible\n");
        else
            printf("Not Sure\n");

    }
    return 0;


}