题意：有一个ACM工厂会生产一些电脑，在这个工厂里面有一些生产线，分别生产不同的零件，不过他们生产的电脑可能是一体机，所以只能一些零件加工后别的生产线才可以继续加工，比如产品A在生产线1号加工后继续前往生产线2号继续加工，直到成为完全产品。输入 P 意思是这个电脑需要P个零件，N表示有N个生产线，每个生产线都有最大加工量，并且需要什么零件和输出的是什么零件，0表示没有这个零件，1表示有这个零件，2表示有没有都可以。
样例说明：
3 4
1号： 15
0 0 0
-->
0 1 0
2号： 10
0 0 0
-->
0 1 1
3号： 30
0 1 2
-->
1 1 1
4号： 3
0 2 1
-->
1 1 1
1号生产线需要0 0 0这样的零件（这样的零件也就是无限制零件，源点），它可以把零件加工成 0 1 0 这个样子，然后 3 号生产线可以接受这种零件，并且加工成 1 1 1 也就是成品，到这样也就加工成功了，因为1号生产线每次可以加工 15 个零件，所以1->3的加工量就是 15，同理 2->3的加工量是 10，所以结果是 25。
分析：很明显的网络流题目，感觉难点应该在题目阅读和建图上.....可以用0当做源点 N+1当做汇点，然后每两点都进行匹配一些，看看是否可以连接，路径的权值为出点的生产能力。
注意：因为每个生产线的生产能力有限，所以需要拆点，防止超出他的生产能力，比如下图如果不拆点结果就会使20，实际上是10
还有一定一定要注意的输入输出没有 “
Sample output 1” “
Sample output 1
”！！！！就是这个坑我错了好多次
/**************************分割线**************分割线**************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; const int MAXN = ;
const int oo = 1e9+; int G[MAXN][MAXN], layer[MAXN], G1[MAXN][MAXN];
int P, N;///需要P个零件，N条生产线
///表示生产线，需要的零件in，输出的零件out，最大生产值Flow
struct node{int in[MAXN], out[MAXN], Flow;}a[MAXN]; void InIt()
{
memset(G, false, sizeof(G));
memset(G1, false, sizeof(G1)); for(int i=; i<=P; i++)
{
a[].out[i] = ;
a[].in[i] = ;
a[N+].in[i] = ;
a[N+].out[i] = ;
}
a[].Flow = oo;
a[N+].Flow = oo;
}
bool canLink(node n1, node n2)
{///n1输出的零件是否是n2需要的
for(int i=; i<=P; i++)
{
if(n1.out[i] != n2.in[i] && n2.in[i] != )
return false;
} return true;
}
bool bfs(int start, int End)
{
int used[MAXN] = {};
queue<int> Q;Q.push(start);
memset(layer, -, sizeof(layer));
used[start] = true, layer[start] = ; while(Q.size())
{
int u = Q.front();Q.pop(); if(u == End)return true; for(int i=; i<=End; i++)
{
if(G[u][i] && !used[i])
{
used[i] = true;
layer[i] = layer[u] + ;
Q.push(i);
}
}
} return false;
}
int dfs(int u, int MaxFlow, int End)
{
if(u == End)return MaxFlow; int uFlow = ; for(int i=; i<=End; i++)
{
if(layer[u]+==layer[i] && G[u][i])
{
int flow = min(MaxFlow-uFlow, G[u][i]);
flow = dfs(i, flow, End); G[u][i] -= flow;
G[i][u] += flow;
uFlow += flow; if(uFlow == MaxFlow)
break;
}
} return uFlow;
}
int dinic(int start, int End)
{
int MaxFlow = ; while(bfs(start, End) == true)
MaxFlow += dfs(start, oo, End); return MaxFlow;
} int main()
{
while(scanf("%d%d", &P, &N) != EOF)
{
int i, j; InIt(); for(i=; i<=N+; i++)
{
scanf("%d", &a[i].Flow);
for(j=; j<=P; j++)
scanf("%d", &a[i].in[j]);
for(j=; j<=P; j++)
scanf("%d", &a[i].out[j]);
} N+=; for(i=; i<=N; i++)
for(j=; j<=N; j++)
{
if(i == j)
{
G1[i][j+N] = G[i][j+N] = a[i].Flow;
}
else if(i!=j && canLink(a[i], a[j]) == true)
{
G1[i+N][j] = G[i+N][j] = a[i].Flow;
}
} int MaxFlow = dinic(, N*);
int k=, x[MAXN], y[MAXN], flow[MAXN]; for(i=; i<N; i++)
for(j=; j<N; j++)
{
if(G[i+N][j] < G1[i+N][j])
{
x[k] = i;
y[k] = j;
flow[k++] = G1[i+N][j] - G[i+N][j];
}
} printf("%d %d\n", MaxFlow, k);
for(i=; i<k; i++)
printf("%d %d %d\n", x[i]-, y[i]-, flow[i]);
} return ;
}
/**
输入 3 5
10 0 0 0 0 1 0
10 0 0 0 0 1 0
10 0 1 0 0 1 1
10 0 1 1 1 1 1
10 0 1 1 1 1 1 输出 10 2
1 3 10
3 4 10 **/