題意：每臺電腦共有p種零件，現在有n臺機器，給出n臺機器每臺需要的一些種類零件當原料(0代表不需要，1代表必須要，2代表可有可無）和輸出的產品零件。問怎么安排生產線使生產出來零件可以組裝的電腦最多。

思路：如果機器的原材料什么都不需要的話就可以當源點，如果機器輸出的零件種類為p就可以當匯點。剛開始想復雜了（1 0 1 可以同時跟1 0 0和0 0 1相連），這題只有當一臺機器的輸出格式跟另一臺的輸入格式一樣時才可以相連，不能有多余的零件產生。最后想想如果不是這樣的話，2代表的可有可無就沒意義了。當p=3時，輸出1 0 1不能跟1 0 0相連但可以跟1 0 2相連。

?

#include<stdio.h> #include<string.h> const int N=100; const int inf=0x3fffffff; 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].st=x;ee[num].ed=y;ee[num].flow=w;e[num].st=x;e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++;e[num].st=y;e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++; } struct node {int in[11],out[11],w; }p[N]; int dfs(int u,int minflow) {if(u==end)return minflow;int i,flow=0,f,v,min_dis=ans-1;for(i=head[u];i!=-1;i=e[i].next){if(e[i].flow<=0)continue;v=e[i].ed;if(dis[v]+1==dis[u]){f=dfs(v,e[i].flow>minflow-flow?minflow-flow:e[i].flow);e[i].flow-=f;e[i^1].flow+=f;flow+=f;if(flow==minflow)break;if(dis[start]>=ans)return flow;}min_dis=min_dis>dis[v]?dis[v]:min_dis;} if(flow==0){if(--gap[dis[u]]==0)dis[start]=ans;dis[u]=min_dis+1;gap[dis[u]]++;}return flow; } int isap() {int maxflow=0;memset(dis,0,sizeof(dis));memset(gap,0,sizeof(gap));gap[0]=ans;while(dis[start]<ans)maxflow+=dfs(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));start=0,end=n+1;ans=end+1;num=0;for(i=1;i<=n;i++){flag=0;scanf("%d",&p[i].w);for(j=0;j<m;j++){scanf("%d",&p[i].in[j]);if(p[i].in[j]==1)flag=1;}if(flag==0)//如果什么原料都不要就與超級源點相連addedge(start,i,p[i].w);flag=0;for(j=0;j<m;j++){scanf("%d",&p[i].out[j]);if(p[i].out[j]==0)flag=1;}if(flag==0)//如果能生產所有的零件跟匯點相連addedge(i,end,p[i].w);}for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(j==i)continue;for(k=0;k<m;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(k==m)addedge(i,j,p[i].w);}}maxflow=isap();sum=0;for(i=0;i<num;i+=2){if(e[i].st==start||e[i].ed==end)continue;if(e[i].flow<ee[i].flow)//如果邊的流量變小的，就有流量走過pp[sum++]=i;}printf("%d %d\n",maxflow,sum);for(j=0;j<sum;j++){i=pp[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

總結

以上是生活随笔為你收集整理的poj 3436 (最大流)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。