题意：
一共有N个机器，每个机器有P个元素，对应输入的时候输入N个机器的信息，第一个数表示这个机器可以一共能够生产多少产物，接下来2p个元素，前p个元素：其中有三种数值，1,2,0，分别表示必须有这个位子的组件，可有可没有这个位子的组件，以及不能有这个位子的组件。一个中间产物想在这个机器上进行生产接下来的产物，必须要满足这些条件才行，对应在这个机器上产生的产物的各个组件的结果是后p个元素。
solution:
1 #include2 #include 3 #include 4 #include 5 #define FRE(name) freopen(#name".txt","r",stdin); 6 using namespace std; 7 const int N=1.5e4+5,M=55; 8 const int INF=0x3f3f3f3f; 9 struct edge{ int u,v,cap,next;}e[N*100],last[N*100];int tot=0; 10 int n,p,S,T,cnt,head[N],dep[N],val[N],res[N*100][3],in[M][N],out[M][N],q[N*50]; 11 void add(int x,int y,int z){ 12 e[tot].u=x;e[tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot++; 13 e[tot].u=y;e[tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot++; 14 } 15 bool isNULL(int *in){ //与源点相连 16 for(int i=1;i<=p;i++) if(in[i]==1) return 0; 17 return 1; 18 } 19 bool isFULL(int *out){ //与源点相连 20 for(int i=1;i<=p;i++) if(!out[i]) return 0; 21 return 1; 22 } 23 bool canLink(int *out,int *in){ //普通节点之间的相连 24 for(int i=1;i<=p;i++) if(in[i]+out[i]==1) return 0; 25 return 1; 26 } 27 void mapping(){ 28 S=0,T=n+1; 29 for(int i=1;i<=n;i++){ 30 if(isNULL(in[i])) add(S,i,val[i]); 31 if(isFULL(out[i])) add(i,T,val[i]); 32 } 33 for(int i=1;i<=n;i++){ 34 for(int j=1;j<=n;j++){ 35 if(i==j) continue; 36 if(canLink(out[i],in[j])) add(i,j,val[i]); 37 } 38 } 39 } 40 bool bfs(){ 41 for(int i=S;i<=T;i++) dep[i]=-1; 42 int h=0,t=1;dep[S]=0;q[t]=S; 43 while(h!=t){ 44 int x=q[++h]; 45 for(int i=head[x];~i;i=e[i].next){ 46 if(dep[e[i].v]==-1&&e[i].cap){ 47 dep[e[i].v]=dep[x]+1; 48 if(e[i].v==T) return 1; 49 q[++t]=e[i].v; 50 } 51 } 52 } 53 return 0; 54 } 55 int dfs(int x,int f){ 56 if(x==T) return f; 57 int used=0,t; 58 for(int i=head[x];~i;i=e[i].next){ 59 if(e[i].cap&&dep[e[i].v]==dep[x]+1){ 60 t=dfs(e[i].v,min(e[i].cap,f)); 61 e[i].cap-=t;e[i^1].cap+=t; 62 used+=t;f-=t; 63 if(!f) return used; 64 } 65 } 66 if(!used) dep[x]=-1; 67 return used; 68 } 69 void dinic(){ 70 int ans=0; 71 while(bfs()) ans+=dfs(S,INF); 72 printf("%d ",ans); 73 } 74 void init(){ 75 tot=0;cnt=0; 76 memset(head,-1,sizeof head); 77 } 78 int main(){ 79 //FRE(sh); 80 while(scanf("%d%d",&p,&n)==2){ 81 init(); 82 for(int i=1;i<=n;i++){ 83 scanf("%d",&val[i]); 84 for(int j=1;j<=p;j++) scanf("%d",&in[i][j]); 85 for(int j=1;j<=p;j++) scanf("%d",&out[i][j]); 86 } 87 mapping(); 88 memcpy(last,e,sizeof e); 89 dinic(); 90 for(int i=0;i