poj3436 ACM Computer Factory

题意：

　　n个工厂加工电脑，电脑有p个部件。每个工厂加工的电脑必须是满足它对原材料的需求。p个部件，0代表不能有，1必须有，2代表可有可无。然后经过加工后，这个工厂输出的电脑各个部件的情况，0代表没有，1代表有。每个工厂有一个生产效率。求单位时间内的最多能生产的完整电脑数量。

解决：

　　每个工厂拆成两个点，流量为该工厂效率。超级源连接对p个部件需求都为0的工厂，超级汇连接输出p个部件都为1的工厂。求一次最大流。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <climits>
  5 
  6 const int MAXN = 100 + 20;
  7 const int INF = INT_MAX;
  8 
  9 int g[MAXN];
 10 
 11 int n, p;
 12 
 13 struct Mach{
 14     int q, in[11], out[11];
 15 }mach[MAXN<<2];
 16 
 17 struct Edge{
 18     int v, f, pre;
 19 }e[MAXN*MAXN], e_bak[MAXN*MAXN];
 20 int e_n;
 21 
 22 struct Flow{
 23     int u, v, f;
 24 }flow[MAXN<<2];
 25 int f_e;
 26 
 27 int layer[MAXN];
 28 
 29 int dfs(int u, int sink, int flow)
 30 {
 31     if(u == sink)
 32         return flow;
 33     int now_flow = 0;
 34     for(int i = g[u]; i && flow; i = e[i].pre){
 35         int v = e[i].v;
 36         int f = e[i].f;
 37         if(f > 0 && layer[v] == layer[u] + 1){
 38             int d = dfs(v, sink, std::min(f, flow));
 39             e[i].f -= d;
 40             e[i^1].f += d;
 41             flow -= d;
 42             now_flow += d;
 43         }
 44     }
 45     return now_flow;
 46 }
 47 
 48 void bfs(int src, int sink)
 49 {
 50     memset(layer, -1, sizeof layer);
 51     std::queue<int> que;
 52     que.push(src);
 53     layer[src] = 0;
 54     while(que.empty() == false){
 55         int u = que.front();
 56         que.pop();
 57         for(int i = g[u]; i; i = e[i].pre){
 58             int v = e[i].v;
 59             int f = e[i].f;
 60             if(f > 0 && layer[v] == -1){
 61                 que.push(v);
 62                 layer[v] = layer[u] + 1;
 63             }
 64         }
 65     }
 66 }
 67 
 68 int dinic(int src, int sink)
 69 {
 70     int res = 0;
 71     while(true){
 72         bfs(src, sink);
 73         if(layer[sink] == -1){
 74             return res;
 75         }
 76         res += dfs(src, sink, INF);
 77     }
 78 }
 79 
 80 
 81 
 82 void addEdge(int u, int v, int f)
 83 {
 84     ++ e_n;
 85     e[e_n].v = v;
 86     e[e_n].f = f;
 87     e[e_n].pre = g[u];
 88     g[u] = e_n;
 89     
 90     ++e_n;
 91     e[e_n].v = u;
 92     e[e_n].f = 0;
 93     e[e_n].pre = g[v];
 94     g[v] = e_n;
 95 }
 96 
 97 void init()
 98 {
 99     e_n = 1;
100     f_e = 0;
101     memset(g, 0, sizeof g);
102     memset(e, 0, sizeof e);
103     memset(e_bak, 0, sizeof e_bak);
104     memset(flow, 0, sizeof flow);
105     memset(mach, 0, sizeof mach);
106 }
107 
108 int main()
109 {
110     while(~scanf("%d%d", &p, &n)){
111         init();
112         //scanf("%d%d", &p, &n);
113         int src = 0;
114         int sink = n*2+1;
115         // input
116         for(int i = 1; i <= n; ++ i){
117             scanf("%d", &mach[i].q);
118             for(int j = 1; j <= p; ++ j){
119                 scanf("%d", &mach[i].in[j]);
120             }
121             for(int j = 1; j <= p; ++ j){
122                 scanf("%d", &mach[i].out[j]);
123             }    
124             addEdge(i, i+n, mach[i].q);
125         }
126         // addEdge
127         for(int i = 1; i <= n; ++ i){
128             bool ok = true;
129             for(int j = 1; j <= p; ++ j){
130                 if(mach[i].in[j] == 1){
131                     ok = false;
132                     break;
133                 }
134             }
135             if(ok == true){
136                 addEdge(src, i, INF);
137             }
138     
139             ok = true;
140             for(int j = 1; j <= p; ++ j){
141                 if(mach[i].out[j] != 1){
142                     ok = false;
143                     break;
144                 }
145             }
146             if(ok == true){
147                 addEdge(i+n, sink, INF);
148             }
149     
150             for(int j = 1; j <= n; ++ j){
151                 if(i == j){
152                     continue;
153                 }
154                 ok = true;
155                 for(int k = 1; k <= p; ++ k){
156                     if(mach[i].in[k] == 1 && mach[j].out[k] == 0){
157                         ok = false;
158                         break;
159                     }
160                     if(mach[i].in[k] == 0 && mach[j].out[k] == 1){
161                 
162                         ok = false;
163                         break;
164                     }
165                 }
166                 if(ok == true){
167                     addEdge(j+n, i, INF);
168                 }
169             }
170         }
171     
172         for(int i = 2; i <= e_n; ++ i){
173             e_bak[i] = e[i];
174         }
175 
176         printf("%d ", dinic(src, sink));
177 
178         for(int u = n+1; u <= n*2; ++ u){
179             for(int i = g[u]; i; i = e[i].pre){
180                 int v = e[i].v;
181                 if(v == 0 || v > n)
182                     continue;
183                 int f = e[i].f;
184                 int f_bak = e_bak[i].f;
185                 if(f_bak > f){
186                     f_e ++;
187                     flow[f_e].u = u-n;
188                     flow[f_e].v = v;
189                     flow[f_e].f = f_bak - f;
190                 }
191             }
192         }
193         printf("%d
", f_e);
194         for(int i = 1; i <= f_e; ++ i){
195             printf("%d %d %d
", flow[i].u, flow[i].v, flow[i].f);
196         }
197     }
198 }