POJ 3436 ACM Computer Factory（Dinic）

本文主要是介绍POJ 3436 ACM Computer Factory（Dinic），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

电脑公司生产电脑有N个机器，每个机器单位时间产量为Qi。 电脑由P个部件组成，每个机器工作时只能把有某些部件的半成品电脑(或什么都没有的空电脑）变成有另一些部件的半成品电脑或完整电脑(也可能移除某些部件）。求电脑公司的单位时间最大产量，以及哪些机器有协作关系，即一台机器把它的产品交给哪些机器加工。

输入描述了机器在组装计算机时那些部件必须准备好了，输入是由P个整数组成，每个整数代表一个部件，这些整数的取值为0,1和3，其中0表示该部件不应该被准备好，1标志该部件必须准备好了，2表示该部件是否准备好无关紧要。

Sample input

3 4

15 0 0 0 0 1 0

10 0 0 0 0 1 1

30 0 1 2 1 1 1
3   0 2 1 1 1 1

Sample output

25 2

1 3 15

2 3 10

输入：电脑由3个部件组成，共有4台机器，1号机器产量15, 能给空电脑加上2号部件，2号 机器能给空电脑加上2号部件和3号部件, 3号机器能把有1个2号部件和3号部件有无均可的电脑变成成品（每种部件各有一个）
输出：单位时间最大产量25,有两台机器有协作关系，
1号机器单位时间内要将15个电脑给3号机器加工
2号机器单位时间内要将10个电脑给3号机器加工

建模分析：
每个工厂有三个动作：
1) 接收原材料
2) 生产
3) 将其产出的半成品给其他机器，或产出成品。
 这三个过程都对应不同的流量。

思路：

网络流模型：

1) 添加一个原点S,S提供最初的原料 00000...
2) 添加一个汇点T, T接受最终的产品 11111...
3) 将每个机器拆成两个点: 编号为i的接收节点，和编号为i+n的产出节点（n是机器数目），前者用于接收原料，后者用于提供加工后的半成品或成品。这两个点之间要连一条边，容量为单位时间产量Qi
4) S 连边到所有接收 "0000..." 或 "若干个0及若干个2" 的机器，容量为无穷大
5) 产出节点连边到能接受其产品的接收节点，容量无穷大
6) 能产出成品的节点，连边到T，容量无穷大。
7) 求S到T的最大流

拿第一组数据建模

15 0 0 0 0 1 0
10 0 0 0 0 1 1
30 0 1 2 1 1 1
3   0 2 1 1 1 1

网络流的难点就在于如何去建模，建模建好了剩下的就是去套模板

Dinic：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
#define MAXN 110
#define INF 0x3f3f3f3f
int n,m,p,s,t;
int vis[MAXN],alpha[MAXN];
int G [MAXN][MAXN],sign[MAXN];
int mp[MAXN][MAXN],G_copy[MAXN][MAXN];
struct node
{int x,y,c;
};
int check1(int a[])
{if(a[1]==0){for(int i=1; i<=p; i++)if(a[i]!=0) return 0;}else if(a[1]==2){for(int i=1; i<=p; i++)if(a[i]!=2) return 0;}else return 0;return 1;
}
int check2(int a[])
{for(int i=1; i<=p; i++)if(a[i]!=1) return 0;return 1;
}
int Union(int a[],int b[])
{for(int i=1; i<=p; i++){if(a[i]+b[i]==1)return 0;}return 1;
}
//建立层次网络
int Countsign()
{memset(sign,-1,sizeof(sign));queue<int>Q;Q.push(s);sign[s]=0;while(!Q.empty()){int v=Q.front();Q.pop();for(int i=s; i<=t; i++){if(sign[i]==-1&&G[v][i]>0){sign[i]=sign[v]+1;Q.push(i);}}}if(sign[t]==-1) return 0;return 1;
}
void Dinic()
{int i,j,maxflow=0;m=0;while(Countsign()){memset(vis,0,sizeof(vis));deque<int>q;q.push_back(s);vis[s]=1;while(!q.empty()){int nd=q.back();if(nd==t)//nd是汇点{int minc=INF;int minvs;for(i=1; i<q.size(); i++){int vs=q[i-1];int ve=q[i];if(G[vs][ve]<minc&&G[vs][ve]>0){minc=G[vs][ve];minvs=vs;}}maxflow+=minc;for(i=1; i<q.size(); i++){int vs=q[i-1];int ve=q[i];G[vs][ve]-=minc;//修改流量网络G[ve][vs]+=minc;//建立反向边}while(!q.empty()&&q.back()!=minvs){vis[q.back()]=0;q.pop_back();}}else//nd不是汇点，继续dfs{for(i=0; i<=t; i++){if(G[nd][i]>0&&!vis[i]&&sign[i]==sign[nd]+1){q.push_back(i);vis[i]=1;break;}}if(i>t) q.pop_back();}}}printf("%d ",maxflow);
}
int main()
{int i,j;while(~scanf("%d%d",&p,&n)){s=0,t=2*n+1;//源点和汇点memset(G,0,sizeof(G));memset(mp,0,sizeof(mp));memset(alpha,0,sizeof(alpha));for(i=1; i<=n; i++){scanf("%d",&alpha[i]);for(j=1; j<=p; j++)scanf("%d",&mp[i][j]);for(j=1; j<=p; j++)scanf("%d",&mp[i+n][j]);//i->i+n建立一条边G[i][i+n]=alpha[i];//源点是否可以连接i点，若可以流量为INFif( check1(mp[i]) )G[s][i]=INF;//i+n是否符合输出条件，若可以与汇点建立流量为INF的边if( check2(mp[i+n]) )G[i+n][t]=INF;}//j->i可以建立生产顺序for(i=n+1; i<=2*n; i++){for(j=1; j<=n; j++){if(i-n==j) continue;if(Union(mp[i],mp[j]))G[i][j]=INF;}}//用于输出最大流中每条边的流量for(i=s; i<=t; i++)for(j=s; j<=t; j++)G_copy[i][j]=G[i][j];Dinic();int cnt=0;vector<node>v;for(i=n+1; i<=2*n; i++)for(j=1; j<=n; j++){if(i-n!=j&&G[i][j]!=G_copy[i][j]){cnt++;node tmp;tmp.x=i-n;tmp.y=j;tmp.c=G_copy[i][j]-G[i][j];v.push_back(tmp);}}printf("%d\n",cnt);for(i=0; i<v.size(); i++)printf("%d %d %d\n",v[i].x,v[i].y,v[i].c);}return 0;
}

这篇关于POJ 3436 ACM Computer Factory（Dinic）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---