kuangbin专题专题十一 网络流 POJ 3436 ACM Computer Factory
SSummerZzz 人气:5题目链接：https://vjudge.net/problem/POJ-3436
Sample input 1 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
题目：P —— 一台电脑由p个零件组成
N —— 工厂有n台加工组装电脑的机器
Q ——— i-th机器每单位时间能工作的数量
当每个未成品需要放入某个机器进一步加工的时候，它需要满足这台机器能正常工作的前提，
即它必须满足某些零件已经组装好了。
样例1： 前p个数字表示，进入i-th台机器，必须满足这些条件（0表示这个零件不能被安装 1表示这个零件必须被安装 2表示这个零件有无被安装无影响）
后p个数字表示，某个未成品被i-th台机器加工完成后，满足了这些条件（0表示这个零件没被安装 1表示这个零件被安装了）
问：怎么安排机器工作方案，能使得工作效率最大化，安排情况有很多，输出一种即可。
思路：比较清楚，一个超级源点，一个超级汇点，一台机器需要拆成入点和出点，一台机器的入点和出点流量为该机器单位时间的工作量，其他点与点之间的流量就是INF了。
重点就是哪些边能建立起来比较麻烦，图建好了，跑一个Dinic就OK了。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <queue>
5 #include <vector>
6 using namespace std;
7
8 const int N = 110,INF = (int)1e9;
9 int p,n,tot;
10 int G[N][N],head[N],lev[N];
11 queue<int > que;
12 struct info{
13 int in[20],out[20];
14 int cap;
15 }info[N];//存机器的信息
16 struct node{
17 int to,nxt,flow;
18 }e[N*N];
19
20 void init_main(){
21 for(int i = 1; i <= n; ++i)
22 for(int j = 1; j <= n; ++j) G[i][j] = 0;
23
24 for(int i = 0; i <= 2*n+1; ++i) head[i] = -1; tot = 0;
25 }
26
27 void init_bfs(){
28 for(int i = 1; i <= 2*n+1; ++i) lev[i] = 0;
29 while(!que.empty()) que.pop();
30 }
31
32 inline void add(int u,int v,int flow){
33 e[tot].to = v;
34 e[tot].flow = flow;
35 e[tot].nxt = head[u];
36 head[u] = tot++;
37 }
38
39 //是否可连边
40 inline bool check(int x,int y){
41 for(int i = 1; i <= p; ++i){
42 if(info[y].in[i] == 2) continue;
43 if(info[x].out[i] != info[y].in[i]) return false;
44 }
45 return true;
46 }
47
48 //建边
49 void rebuild(){
50 for(int i = 1; i <= n; ++i){
51 if(check(0,i)){
52 add(0,i,INF); add(i,0,0);
53 }
54 if(check(i,2*n+1)){
55 add(i+n,2*n+1,INF); add(2*n+1,i+n,0);
56 }
57 }
58 for(int i = 1; i <= n; ++i){
59 for(int j = 1; j <= n; ++j){
60 if(i == j){
61 add(i,i+n,info[i].cap); add(i+n,i,0);
62 }
63 else if(check(i,j)){
64 add(i+n,j,INF); add(j,i+n,0);
65 }
66 }
67 }
68 }
69
70 int dfs(int now,int flow,int t){
71 if(now == t) return flow;
72 int to,sum = 0,tmp = 0;
73 for(int o = head[now]; ~o; o = e[o].nxt){
74 to = e[o].to;
75 if((lev[to] == lev[now] +1) && e[o].flow && (tmp = dfs(to,min(flow - sum, e[o].flow),t))){
76 //需要的路径流量 G数组来存机器之间的联系
77 if(now > n && now < 2*n+1 && to != 2*n+1){
78 G[now-n][to] += tmp;
79 }
80 e[o].flow -= tmp;
81 e[o^1].flow += tmp;
82 if((sum += tmp) == flow) return sum;
83 }
84 }
85 return sum;
86 }
87
88 bool bfs(int s,int t){
89 init_bfs();
90 que.push(0);
91 while(!que.empty()){
92 int now = que.front(); que.pop();
93 for(int o = head[now]; ~o; o = e[o].nxt){
94 int to = e[o].to;
95 if(!lev[to] && e[o].flow){
96 lev[to] = lev[now] + 1;
97 que.push(to);
98 }
99 }
100 }
101 if(lev[t]) return true;
102 else return false;
103 }
104
105 int mf(int s,int t){
106 int max_flow = 0;
107 while(bfs(s,t)){
108 max_flow += dfs(s,INF,t);
109 //cout << "max_flow " << max_flow << endl;
110 }
111 return max_flow;
112 }
113
114 int main(){
115
116 while(~scanf("%d%d",&p,&n)){
117 init_main();
118 //读入信息 0超级源点 2*n+1超级汇点
119 for(int i = 1; i <= n; ++i){
120 scanf("%d",&info[i].cap);
121 for(int j = 1; j <= p; ++j) scanf("%d",&info[i].in[j]);
122 for(int j = 1; j <= p; ++j) scanf("%d",&info[i].out[j]);
123 }
124 info[0].cap = INF; info[2*n+1].cap = INF;
125 for(int i = 1; i <= p; ++i){
126 info[0].out[i] = 0;
127 info[2*n+1].in[i] = 1;
128 }
129 //建图
130 rebuild();
131 //Dinic
132 int _mf = mf(0,2*n+1),line = 0;
133 //统计需要的联系数量
134 for(int i = 1; i <= n; ++i){
135 for(int j = 1; j <= n; ++j){
136 if(G[i][j]) ++line;
137 }
138 }
139 printf("%d %d\n",_mf,line);
140 //输出联系
141 for(int i = 1; i <= n; ++i){
142 for(int j = 1; j <= n; ++j){
143 if(G[i][j]) printf("%d %d %d\n",i,j,G[i][j]);
144 }
145 }
146 }
147
148 return 0;
149 }
加载全部内容