泊头市做网站价格,重新装wordpress,网站域名 安全,wordpress 传值题意#xff1a;每台电脑共有p种零件#xff0c;现在有n台机器#xff0c;给出n台机器每台需要的一些种类零件当原料(0代表不需要#xff0c;1代表必须要#xff0c;2代表可有可无#xff09;和输出的产品零件。问怎么安排生产线使生产出来零件可以组装的电脑最多。 思路…题意每台电脑共有p种零件现在有n台机器给出n台机器每台需要的一些种类零件当原料(0代表不需要1代表必须要2代表可有可无和输出的产品零件。问怎么安排生产线使生产出来零件可以组装的电脑最多。 思路如果机器的原材料什么都不需要的话就可以当源点如果机器输出的零件种类为p就可以当汇点。刚开始想复杂了1 0 1 可以同时跟1 0 0和0 0 1相连这题只有当一台机器的输出格式跟另一台的输入格式一样时才可以相连不能有多余的零件产生。最后想想如果不是这样的话2代表的可有可无就没意义了。当p3时输出1 0 1不能跟1 0 0相连但可以跟1 0 2相连。 #includestdio.h
#includestring.h
const int N100;
const int inf0x3fffffff;
int gap[N],dis[N],head[N],num,start,end,ans,pp[N*N];
struct edge
{int st,ed,flow,next;
}e[N*N],ee[N*N];
void addedge(int x,int y,int w)
{ee[num].stx;ee[num].edy;ee[num].floww;e[num].stx;e[num].edy;e[num].floww;e[num].nexthead[x];head[x]num;e[num].sty;e[num].edx;e[num].flow0;e[num].nexthead[y];head[y]num;
}
struct node
{int in[11],out[11],w;
}p[N];
int dfs(int u,int minflow)
{if(uend)return minflow;int i,flow0,f,v,min_disans-1;for(ihead[u];i!-1;ie[i].next){if(e[i].flow0)continue;ve[i].ed;if(dis[v]1dis[u]){fdfs(v,e[i].flowminflow-flow?minflow-flow:e[i].flow);e[i].flow-f;e[i^1].flowf;flowf;if(flowminflow)break;if(dis[start]ans)return flow;}min_dismin_disdis[v]?dis[v]:min_dis;} if(flow0){if(--gap[dis[u]]0)dis[start]ans;dis[u]min_dis1;gap[dis[u]];}return flow;
}
int isap()
{int maxflow0;memset(dis,0,sizeof(dis));memset(gap,0,sizeof(gap));gap[0]ans;while(dis[start]ans)maxflowdfs(start,inf);return maxflow;
}
int main()
{int i,n,m,j,flag,k,sum,maxflow;while(scanf(%d%d,m,n)!-1){memset(head,-1,sizeof(head));start0,endn1;ansend1;num0;for(i1;in;i){flag0;scanf(%d,p[i].w);for(j0;jm;j){scanf(%d,p[i].in[j]);if(p[i].in[j]1)flag1;}if(flag0)//如果什么原料都不要就与超级源点相连addedge(start,i,p[i].w);flag0;for(j0;jm;j){scanf(%d,p[i].out[j]);if(p[i].out[j]0)flag1;}if(flag0)//如果能生产所有的零件跟汇点相连addedge(i,end,p[i].w);}for(i1;in;i){for(j1;jn;j){if(ji)continue;for(k0;km;k){if(p[j].in[k]2)continue;//可有可无的时候不管p[i].out[k]为何值都可以if(p[i].out[k]p[j].in[k])continue;//i的输出要跟j的输入一样break;}if(km)addedge(i,j,p[i].w);}}maxflowisap();sum0;for(i0;inum;i2){if(e[i].ststart||e[i].edend)continue;if(e[i].flowee[i].flow)//如果边的流量变小的就有流量走过pp[sum]i;}printf(%d %d\n,maxflow,sum);for(j0;jsum;j){ipp[j];printf(%d %d %d\n,e[i].st,e[i].ed,ee[i].flow-e[i].flow);}}return 0;
} 转载于:https://www.cnblogs.com/pangblog/p/3331420.html
