http://poj.org/problem?id=3436
每台电脑有$p$个组成部分，有$n$个工厂加工电脑。
每个工厂对于进入工厂的半成品的每个组成部分都有要求，由$p$个数字描述，0代表这个部分不能有，1代表这个部分必须有，2代表这个部分的有无无所谓。
每个工厂的产出也不尽相同，也是由p个数字代表，0代表这个部分不存在，1代表这个部分存在。每个工厂都有一个最大加工量。
给出这$n$个工厂的数据，求出最多能加工出多少台电脑
对于容量有限制,因此拆点
开始的机器没有零件,连接符合要求的点
最终的机器应该是完整的,把符合要求的点连接到汇点
因为已经拆过点限制了流量,所以其余容量记为INF就行了,
关于路径还原 在链式前向星保存边的时候同时记录边的起点,最后反向弧非零的边就是答案
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <iostream>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pp pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)
#define per(ii,a,b) for(int ii=a;ii>=b;ii--)
#define show(x) cout<<#x<<"="<<x<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<b[a]<<endl
using namespace std;
const int maxn=123+10;
const int maxm=1234+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
struct node {int pre,to,cap,next;}e[maxm];
int ss,tt,head[maxn],nume,dis[maxn];
inline void addx(int a,int b,int c){
e[++nume]=(node){a,b,c,head[a]};
head[a]=nume;
}
inline void add(int a,int b,int c){
addx(a,b,c);addx(b,a,0);
}
bool bfs(int s=ss,int t=tt){
int top=0,end=1;
int q[maxn];
q[0]=s;
// for(int i=0;i<=t;i++) dis[i]=0;
memset(dis,0,sizeof dis);
dis[s]=1;
while(top!=end){
int now=q[top++];top%=maxn;
for(int i=head[now];i;i=e[i].next){
int to=e[i].to;
if(!dis[to]&&e[i].cap){
dis[to]=dis[now]+1;
if(to==t)break;
q[end++]=to;end%=maxn;
}
}
}
return dis[t];
}
int dfs(int now=ss,int last=INF){
if(now==tt)return last;
int flow=0,det;
for(int i=head[now];i;i=e[i].next){
int to=e[i].to;
if(e[i].cap&&dis[to]==dis[now]+1){
det=dfs(to,min(last-flow,e[i].cap));
flow+=det;
e[i].cap-=det;
e[i^1].cap+=det;
if(flow==last) return last;
}
}
dis[now]=-1;
return flow;
}
int p;
int cost[123];
int in[123][12];
int out[123][12];
int a[123];
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
nume=1;
IO;
cin>>p>>n;
ss=0,tt=2*n+1;
nume=1;
rep(i,1,n){
cin>>cost[i];
int cnt=0;
rep(j,1,p){
cin>>in[i][j];
if(in[i][j]!=1) cnt++;
}
if(cnt==p) add(ss,i,INF);
cnt=0;
rep(j,1,p){
cin>>out[i][j];
if(out[i][j]==1) cnt++;
}
if(cnt==p) add(i+n,tt,INF);
add(i,i+n,cost[i]);
}
rep(i,1,n){
rep(j,1,n){
if(i==j) continue;
int cnt=0;
rep(k,1,p){
if(in[j][k]!=2&&in[j][k]!=out[i][k]){
cnt++;
break;
}
}
if(cnt==0) add(i+n,j,INF);
}
}
int ans=0;
while(bfs()) ans+=dfs();
if(ans==0) cout<<"0 0\n";
else {
int cnt=0;
for(int i=2;i<=nume;i+=2){
if(abs(e[i].pre-e[i].to)!=n&&e[i].to>ss&&e[i].pre>ss&&e[i].pre<tt&&e[i].to<tt&&e[i^1].cap!=0){
a[cnt++]=i;
}
}
cout<<ans<<' '<<cnt<<'\n';
rep(i,0,cnt-1){
cout<<e[a[i]].pre-n<<' '<<e[a[i]].to<<' '<<e[a[i]^1].cap<<'\n';
}
}
#ifdef test
fclose(stdin);fclose(stdout);system("out.txt");
#endif
return 0;
}