洛谷P 2055[ZJOI 2009]休みの寮(最大流)

トランスファゲート
明らかに二分図の最大マッチングですが、ネットワークストリームが速いようですので、ここではネットワークストリームについて話しましょう.各ベッドの汇点连流量は1の辺で、源点は各学校に住む在校生あるいはその他の学校の学生连流量は1の辺で、各学校に住む学生は自分のベッドと自分の知っている人のベッドに连れて、それから最大の流れを走ります.最大ストリーム=学校に住む学生の数であれば、存在案を示し、逆に存在しない.
Code:

#include
#include
#include

struct node{int x,y,c,next,other;}a[5210];
int n,t,len=0,st,ed,ans=0,tot=0,first[1010],h[1010],q[1010],sch[1010],stay[1010];

void ins(int x,int y,int c)
{
    a[++len]=((node){x,y,c,first[x],len+1});first[x]=len;
    a[++len]=((node){y,x,0,first[y],len-1});first[y]=len;
}

bool bfs()
{
    int head=1,tail=2;q[1]=st;
    memset(h,0,sizeof(h));h[st]=1;
    while(head!=tail)
    {
        int x=q[head];
        for(int i=first[x];i;i=a[i].next)
        {
            int y=a[i].y;
            if(h[y]==0 && a[i].c>0)
            {
                q[tail++]=y;
                h[y]=h[x]+1;
            }
        }
        head++;
    }
    if(h[ed]==0) return false;
    return true;
}

int mymin(int x,int y)
{
    return xint dfs(int x,int flow)
{
    if(x==ed) return flow;
    int tt=0,minf=0;
    for(int i=first[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(a[i].c>0 && h[y]==(h[x]+1) && ttif(tt==0) h[x]=0;
    return tt;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        st=2*n+1;ed=st+1;tot=0;ans=0;len=0;
        memset(first,0,sizeof(first));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&sch[i]);
            if(sch[i]==1) ins(i+n,ed,1);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&stay[i]);
            if((stay[i]==0 && sch[i]==1) || sch[i]==0) tot++,ins(st,i,1);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int x;scanf("%d",&x);
                if(x==1 || i==j) ins(i,j+n,1);
            }
        }
        while(bfs()) ans+=dfs(st,0x3f3f3f3f);
        if(ans==tot) printf("^_^
");
        else printf("T_T
");
    }
}