1 #include<iostream>  2 #include<cstring>  3 #include<queue>  4 #include<cstdio>  5 #include<algorithm>  6 #define min(a,b)(a<b?a:b)  7 #define INF 1000000  8 using namespace std;  9 const int MAX=610; 10 const int N=610; 11 struct Node { 12     int c; 13     int f; 14 }; 15 int sx,ex,p;//sx和ex分别代表源点和汇点 16 int pre[MAX]; 17 Node map[MAX][MAX]; 18 int n,m; 19 bool BFS() { //BFS搜索层次网络 20     memset(pre,0,sizeof(pre)); 21     queue< int > Q; 22     Q.push(sx); 23     pre[sx]=1; 24     while(!Q.empty()) { 25         int d=Q.front(); 26         Q.pop(); 27         for(int i=0; i<=2*n+1; i++) { 28             if(!pre[i]&&map[d][i].c-map[d][i].f) { 29                 pre[i]=pre[d]+1; 30                 Q.push(i); 31             } 32         } 33     } 34     return pre[ex]!=0; 35 } 36 int dinic(int pos,int flow) { //pos是顶点号，flow是当前顶点所能得到的流量,一次dinic只能求出一次增加的流量， 37     int f=flow; 38     if(pos==ex) 39         return flow; 40     for(int i=0; i<=2*n+1; i++) { 41         if(map[pos][i].c-map[pos][i].f&&pre[pos]+1==pre[i]) { 42             int a=map[pos][i].c-map[pos][i].f; 43             int t=dinic(i,min(a,flow)); 44             map[pos][i].f+=t; 45             map[i][pos].f-=t; 46             flow-=t; 47             if(flow<=0)break; 48             //我最开始就是这里没弄明白，我不明白为什么要此顶点得到的流量减去改变量； 49             //答案就在下面的  return f-flow; 50         } 51     } 52     if(f-flow<=0)pre[pos]=-1; 53     return f-flow;//其实这里返回给他前一层的就是这个t;因为t在层函数里面都有，所以所过避免重复就写成这样； 54 } 55 int solve(){ 56     int sum=0; 57     while(BFS()) { 58         sum+=dinic(sx,INF); 59         //printf("dada\n"); 60     } 61     return sum; 62 } 63 bool check0(int a[]){ 64     for(int i=1;i<=p;i++){ 65       if(a[i]==1)return false; 66      } 67     return true; 68 } 69 bool checkt(int a[]){ 70     for(int i=1;i<=p;i++){ 71         if(a[i]==0)return false; 72         } 73     return true; 74 } 75 bool check1(int a[],int b[]){ 76     bool flag=true; 77     for(int k=1;k<=p;k++){ 78                 if(a[k]==1 && b[k]==0) 79                     flag=false; 80                 if(a[k]==0 && b[k]==1) 81                     flag=false; 82                 if(!flag) break; 83             } 84       if(flag) 85     return true; 86     else return false; 87 } 88 struct Edge{ 89    int ss[200]; 90 }in[N],out[N]; 91 int val[N],ct; 92 int main(){ 93     while(~scanf("%d%d",&p,&n)){ 94         memset(val,0,sizeof(val)); 95         memset(in,0,sizeof(in)); 96         memset(out,0,sizeof(out)); 97         memset(map,0,sizeof(map)); 98         for(int i=1;i<=n;i++){ 99                scanf("%d",&val[i]);100             for(int j=1;j<=p;j++)101                 scanf("%d",&in[i].ss[j]);102             for(int j=1;j<=p;j++)103                 scanf("%d",&out[i].ss[j]);104         }105             for(int i=1;i<=n;i++){106                 if(check0(in[i].ss))107                   map[0][i].c=INF;108                 if(checkt(out[i].ss))109                     map[i+n][2*n+1].c=INF;110                 }111             for(int i=1;i<=n;i++)112                 for(int j=1;j<=n;j++)113                     if(check1(out[i].ss,in[j].ss)&&i!=j)114                      map[i+n][j].c=INF;115             for(int i=1;i<=n;i++)116                  map[i][i+n].c=val[i];117                ex=2*n+1;sx=0;ct=0;118               int result=solve();119               for(int i=1+n;i<=2*n;i++)120                  for(int j=1;j<=n;j++)121                    if(map[i][j].f>0)122                    ct++;123             printf("%d %d\n",result,ct);124           for(int i=1+n;i<=2*n;i++)125                  for(int j=1;j<=n;j++)126                    if(map[i][j].f>0){127                     printf("%d %d %d\n",i-n,j,map[i][j].f);128                    }129 130         }131       return 0;132 133 }