学步园

//Time 47ms, Memory 308K

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0xfffffff;
queue<int>q;
int cap[55][55],flow[55][55],d[2505],e[2505],n,p,cnt=0,vis[55][55];
void f1(int i)
{
    int j;
    for(j=1;j<=n;j++) if(i!=j && flow[i][j]>0 && !vis[i][j])
    {
        vis[i][j]=1;
        if(i)
        {
            cnt++;d[cnt]=i;e[cnt]=j;
        }
        f1(j);
    }
}
int main()
{
    int i,j,k,pp[55],a[55],b[55][12],c[55][12],s=0,t;
    cin>>p>>n;
    memset(pp,0,sizeof(pp));
    memset(cap,0,sizeof(cap));
    memset(flow,0,sizeof(flow));
    memset(vis,0,sizeof(vis));
    t=n+1;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        for(j=0;j<p;j++)
            cin>>b[i][j];
        for(j=0;j<p;j++)
            cin>>c[i][j];
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<p;j++)
            if(b[i][j]==1) break;
        if(j==p) cap[s][i]=a[i];
        for(j=0;j<p;j++)
            if(c[i][j]==0) break;
        if(j==p) cap[i][t]=a[i];
        else
        {
            for(j=1;j<=n;j++) if(i!=j)
            {
                for(k=0;k<p;k++)
                    if(c[i][k]+b[j][k]==1) break;
                if(k==p) cap[i][j]=a[i];
            }
        }
    }
    int f=0;
    for(;;)
    {
        memset(a,0,sizeof(a));
        a[s]=inf;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int v=1;v<n+2;v++) if(!a[v] && cap[u][v]>flow[u][v])
            {
                pp[v]=u;q.push(v);
                int tt=cap[u][v]-flow[u][v];
                a[v]=a[u]<tt?a[u]:tt;
            }
        }
        if(a[t]==0) break;
        for(int u=t;u!=s;u=pp[u])
        {
            flow[pp[u]][u]+=a[t];
            flow[u][pp[u]]-=a[t];
        }
        f+=a[t];
    }
    f1(s);
    cout<<f<<" "<<cnt<<endl;
    for(i=1;i<=cnt;i++) if(d[i])
    {
        cout<<d[i]<<" "<<e[i]<<" "<<flow[d[i]][e[i]]<<endl;
    }
    return 0;
}