首页 > 代码库 > poj3436 Computer Factory

poj3436 Computer Factory

2024-09-02 14:29:02   219人阅读

题意：

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

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

实现：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 
  7 const int INF = 0x3f3f3f3f;
  8 
  9 int g[105][15], p, n, q[55];
 10 int G[105][105], G_copy[105][105], layer[105], vis[105];
 11 
 12 struct node
 13 {
 14     int x, y, c;
 15 };
 16 
 17 bool countLayer(int s, int e)
 18 {
 19     layer[s] = 0;
 20     queue<int> q;
 21     q.push(s);
 22     memset(vis, 0, sizeof(vis));
 23     vis[s] = true;
 24     while (!q.empty())
 25     {
 26         int tmp = q.front();
 27         q.pop();
 28         for (int i = 1; i <= e; i++)
 29         {
 30             if (G[tmp][i] && !vis[i])
 31             {
 32                 layer[i] = layer[tmp] + 1;
 33                 if (i == e)
 34                 {
 35                     return true;
 36                 }
 37                 vis[i] = true;
 38                 q.push(i);
 39             }
 40         }
 41     }
 42     return false;
 43 }
 44 
 45 int dinic(int s, int e)
 46 {
 47     int flow = 0;
 48     deque<int> q;
 49     while (countLayer(s, e))
 50     {
 51         memset(vis, 0, sizeof(vis));
 52         vis[s] = true;
 53         q.push_back(s);
 54         while (!q.empty())
 55         {
 56             int tmp = q.back();
 57             if (tmp == e)
 58             {
 59                 int minn = INF;
 60                 int min_index = 0;
 61                 for (int i = 1; i < q.size(); i++)
 62                 {
 63                     if (G[q[i - 1]][q[i]] && G[q[i - 1]][q[i]] < minn)
 64                     {
 65                         minn = G[q[i - 1]][q[i]];
 66                         min_index = i - 1;
 67                     }
 68                 }
 69                 for (int i = 1; i < q.size(); i++)
 70                 {
 71                     G[q[i - 1]][q[i]] -= minn;
 72                     G[q[i]][q[i - 1]] += minn;
 73                 }
 74                 while (q.size() && q.back() != min_index)
 75                 {
 76                     vis[q.back()] = false;
 77                     q.pop_back();
 78                 }
 79                 flow += minn;
 80             }
 81             else
 82             {
 83                 bool flag = false;
 84                 for (int i = 1; i <= e; i++)
 85                 {
 86                     if (G[tmp][i] && !vis[i] && layer[i] == layer[tmp] + 1)
 87                     {
 88                         vis[i] = true;
 89                         q.push_back(i);
 90                         flag = true;
 91                         break;
 92                     }
 93                 }
 94                 if (!flag && q.size())
 95                 {
 96                     q.pop_back();
 97                 }
 98             }
 99         }
100     }
101     return flow;
102 }
103 
104 int main()
105 {
106     while (cin >> p >> n)
107     {
108         for (int i = 0; i < n; i++)
109         {
110             cin >> q[i];
111             for (int j = 0; j < p; j++)
112             {
113                 cin >> g[i][j];
114             }
115             for (int j = 0; j < p; j++)
116             {
117                 cin >> g[i + n][j];
118             }
119         }
120         memset(G, 0, sizeof(G));
121         for (int i = 2; i < n + 2; i++)
122         {
123             G[i][i + n] = q[i - 2];
124         }
125         for (int i = 2; i < n + 2; i++)
126         {
127             bool flag = true;
128             for (int j = 0; j < p; j++)
129             {
130                 if (g[i - 2][j] != 0 && g[i - 2][j] != 2)
131                 {
132                     flag = false;
133                     break;
134                 }
135             }
136             if (flag)
137             {
138                 G[1][i] = INF;
139             }
140         }
141         for (int i = n + 2; i < 2 * n + 2; i++)
142         {
143             bool flag = true;
144             for (int j = 0; j < p; j++)
145             {
146                 if (g[i - 2][j] != 1)
147                 {
148                     flag = false;
149                     break;
150                 }
151             }
152             if (flag)
153             {
154                 G[i][2 * n + 2] = INF;
155             }
156         }
157         for (int i = n + 2; i < 2 * n + 2; i++)
158         {
159             for (int j = 2; j < n + 2; j++)
160             {
161                 bool flag = true;
162                 for (int k = 0; k < p; k++)
163                 {
164                     if (!(g[i - 2][k] == g[j - 2][k] || g[j - 2][k] == 2))
165                     {
166                         flag = false;
167                         break;
168                     }
169                 }
170                 if (flag)
171                 {
172                     G[i][j] = INF;
173                 }
174             }
175         }
176         for (int i = 1; i <= 2 * n + 2; i++)
177         {
178             for (int j = 1; j <= 2 * n + 2; j++)
179             {
180                 G_copy[i][j] = G[i][j];
181             }
182         }
183         cout << dinic(1, 2 * n + 2) << " ";
184         int cnt = 0;
185         vector<node> v;
186         for (int i = n + 2; i < 2 * n + 2; i++)
187         {
188             for (int j = 2; j < n + 2; j++)
189             {
190                 if (i - n != j && G[i][j] != G_copy[i][j])
191                 {
192                     cnt++;
193                     node tmp;
194                     tmp.x = i - n - 1;
195                     tmp.y = j - 1;
196                     tmp.c = G_copy[i][j] - G[i][j];
197                     v.push_back(tmp);
198                 }
199             }
200         }
201         cout << cnt << endl;
202         for (int i = 0; i < v.size(); i++)
203         {
204             cout << v[i].x << " " << v[i].y << " " << v[i].c << endl;
205         }
206     }
207     return 0;
208 }

 

poj3436 Computer Factory


联系
我们