为了追求 ACM 比赛的公平性，所有用作 ACM 比赛的电脑性能是一样的，而 ACM 董事会专门有一条生产线来生产这样的电脑，随着比赛规模的越来越大，生产线的生产能力不能满足需要，所以说 ACM 董事会想要重新建造一条生产线。 生产线是全自动化的，所以需要机器来组成生产线，给定有多少种机器，标准 ACM 用电脑有多少部份，每种机器将什么样的 ACM 电脑半成品处理成什么样的电脑半成品(对于输入的电脑半成品，每部分有 0，1，2 三种状态：代表着 0、这部分必须没有我才能处理，1、这部分必须有我才能处理，2、这部分有没有我都能处理。对于输出的电脑半成品有 0，1 两种状态：代表着 0，处理完后的电脑半成品里没有这部分，1、处理完的电脑半成品有这部分)，每一个机器每小时可以处理 Q 个半成品（输入数据中的 Qi）。 求组装好的成产线的最大工作效率（每小时最多生成多少成品，成品的定义就是所有部分的状态都是“1”） 第一行输入两个数：一个 P 代表有 P 个零件， 一个 N 代表有 N 台机器。 接下来N 行，每行第一个数字有 Qi，代表 第 i 个零件每小时能加工的半成品零件个数。然后是 2*P 个数字，前 P 个数字是加工前半成品需要满足的条件，后 P 个数表示加工后的半成品的数量。
用网络流解决工厂流水线的问题并保存路径。每台机器都有容量，所以把一台机器分成两个点，中间建一条容量的边。同时如果一台机器的输出符合另一台机器的输入，则建一条容量无穷大的边。同时要增加源点和汇点，输入没有 1 的连接源点，输出全是 1 的连接
汇点
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn=1014; const int inf=1e9; int g[maxn][maxn]; int backup[maxn][maxn]; int pre[maxn]; int flow[maxn]; int Line[maxn][3]; int in[maxn][maxn]; int maxflow; int N,M; queue<int> q; void init () { while (!q.empty()) q.pop(); fill (pre,pre+maxn,0); fill (flow,flow+maxn,0); maxflow=0; for (int i=0;i<maxn;i++) for (int j=0;j<maxn;j++) g[i][j]=0; } int bfs (int s,int t) { while (!q.empty()) q.pop(); for (int i=0;i<=N;i++) pre[i]=-1; pre[s]=0; q.push(s); flow[s]=inf; while (!q.empty()) { int x=q.front(); q.pop(); if (x==t) break; for (int i=0;i<=N;i++) { if (g[x][i]!=0&&pre[i]==-1) { pre[i]=x; flow[i]=min(flow[x],g[x][i]); q.push(i); } } } if (pre[t]==-1) return -1; else return flow[t]; } void Edmonds_Karp (int s,int t) { int increase=0; while ((increase=bfs(s,t))!=-1) { int k=t; while (k!=s) { int last=pre[k]; g[last][k]-=increase; g[k][last]+=increase; k=last; } maxflow+=increase; } } int main () { int n,p; while (~scanf("%d %d",&p,&n)) { init (); for (int i=1;i<=n;i++) { for (int j=0;j<2*p+1;j++) scanf ("%d",&in[i][j]); } for (int i=1;i<=n;i++) g[2*i-1][2*i]=in[i][0]; N=2*n+1; for (int i=1;i<=n;i++) { bool flag_s=true; bool flag_t=true; for (int j=0;j<p;j++) { if (in[i][j+1]==1) flag_s=false; if (in[i][j+1+p]==0) flag_t=false; } if (flag_s) g[0][2*i-1]=inf; if (flag_t) g[2*i][N]=inf; for (int j=1;j<=n;j++) { if (i!=j) { bool flag=true; for (int k=0;k<p;k++) if ((in[i][k+p+1]==0&&in[j][k+1]==1)||(in[i][k+p+1]==1&&in[j][k+1]==0)) { flag=false; break; } if (flag) g[2*i][2*j-1]=min(in[i][0],in[j][0]); } } } memcpy (backup,g,sizeof(g)); Edmonds_Karp (0,N); printf ("%d ",maxflow); int ans=0; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (g[2*i][2*j-1]<backup[2*i][2*j-1]) { Line[ans][0]=i; Line[ans][1]=j; Line[ans][2]=backup[2*i][2*j-1]-g[2*i][2*j-1]; ans++; } } } printf ("%d ",ans); for (int i=0;i<ans;i++) printf ("%d %d %d ",Line[i][0],Line[i][1],Line[i][2]); } return 0; }