POJ - 3436
题意：... 大意就是有几台机器可以把半成品加工成成品或者另外的半成品，问你最终每小时得到的最多的成品。
思路：那么由题目，这个机器出来的零件个数和另一个机器需要的零件相同时（2的位置不算），他们肯定有条线，但是这里可以看出，对机器每小时有限制数量，这是对点有限制，而不是对边有限制，所以需要拆点，我第一遍写的时候没拆，但是过了，估计数据比较弱.....
没拆点的：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int maxn = 100,maxe = 1e4 + 50; const int inf = 0x3f3f3f3f; struct ma { int sum,in[12],out[12]; }data[maxn]; struct node { int to,next,cap,rem,rev; node(){} node(int a,int b,int c,int d,int e) {to = a; next = b; cap = c; rem = d;rev = e;} }edge[maxe << 1]; int h[maxn],cur[maxn],deg[maxn]; int out[maxe][3]; int num ,s,t,p,n; void init() { for(int i = 0;i < maxn; i++) h[i] = -1; num = 0; s = 0, t = n+1; } void add(int u,int v,int cap) { edge[num] = node(v,h[u],cap,cap,num+1); h[u] = num++; edge[num] = node(u,h[v],0,0,num-1); h[v] = num++; } void pre() { for(int i = 1; i <= n; i++) { int mark = 1; for(int j = 0; j < p; j++) { if(data[i].in[j] == 2 ) continue; else if(data[i].in[j] == 1) {mark = 0; break;} } if(mark) add(s,i,data[i].sum); } for(int i = 1; i <= n; i++) { int sum = 0; for(int j = 0; j < p; j++) sum += data[i].out[j]; if(sum == p) add(i,t,data[i].sum); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { int mark = 1; for(int k = 0; k < p;k ++) { if(data[j].in[k]==2) continue; else if(data[j].in[k] != data[i].out[k]) {mark = 0; break;} } if(mark) add(i,j,data[i].sum); } } int bfs() { for(int i = 1; i <= n+1; i++) deg[i] = -1; queue<int > q; q.push(s); deg[s] = 0; while(!q.empty()) { int u = q.front(); q.pop(); //cout << "u "<< u <<endl; for(int i = h[u] ;~i; i = edge[i].next) { int v = edge[i].to,rem = edge[i].rem; if(rem && deg[v] == -1) { deg[v] = deg[u] + 1; q.push(v); } } } return deg[t] != -1; } int dfs(int u,int f) { if(u == t) return f; for(int i = cur[u] ;~i; i = edge[i].next) { cur[u] = i; int v = edge[i].to,rem = edge[i].rem,rev = edge[i].rev; if(deg[v] == deg[u]+1 && rem) { int k = dfs(v,min(f,rem)); if(!k) continue; edge[i].rem -= k; edge[rev].rem += k; return k; } } return 0; } void solve() { int flow = 0; while(bfs()) { for(int i = s; i <= t; i++) cur[i] = h[i]; for(;;) { int k = dfs(s,inf); if(k == 0) break; flow += k; } } printf("%d ",flow); int onum = 0; for(int u = 1; u <= n; u++) for(int i = h[u]; ~i; i = edge[i].next) { int v = edge[i].to, rem = edge[i].rem, cap = edge[i].cap; if(cap && rem < cap && v <= n) { out[onum][0] = u, out[onum][1] = v, out[onum++][2] = cap-rem; } } printf("%d\n",onum); for(int i = 0; i < onum; i++) printf("%d %d %d\n", out[i][0] , out[i][1] , out[i][2]); } int main() { while(~scanf("%d%d",&p,&n)) { init(); for(int i = 1; i <= n; i++) { scanf("%d",&data[i].sum); for(int j = 0; j < p; j++) scanf("%d",&data[i].in[j]); for(int j = 0; j < p; j++) scanf("%d",&data[i].out[j]); } pre(); solve(); } return 0; }
拆点 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int maxn = 200,maxe = maxn * maxn + 50; const int inf = 0x3f3f3f3f; struct ma { int sum,in[12],out[12]; }data[maxn]; struct node { int to,next,cap,rem,rev; node(){} node(int a,int b,int c,int d,int e) {to = a; next = b; cap = c; rem = d;rev = e;} }edge[maxe << 1]; int h[maxn],cur[maxn],deg[maxn]; int out[maxe][3]; int num ,s,t,p,n; void init() { for(int i = 0;i < maxn; i++) h[i] = -1; num = 0; s = 0, t = 2*n+1; } void add(int u,int v,int cap) { edge[num] = node(v,h[u],cap,cap,num+1); h[u] = num++; edge[num] = node(u,h[v],0,0,num-1); h[v] = num++; } void pre() { for(int i = 1; i <= n; i++) { int mark = 1; for(int j = 0; j < p; j++) { if(data[i].in[j] == 2 ) continue; else if(data[i].in[j] == 1) {mark = 0; break;} } if(mark) add(s,i,inf); } for(int i = 1; i <= n; i++) add(i,i+n,data[i].sum); for(int i = 1; i <= n; i++) { int sum = 0; for(int j = 0; j < p; j++) sum += data[i].out[j]; if(sum == p) add(i+n,t,inf); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(i==j)continue; int mark = 1; for(int k = 0; k < p;k ++) { if(data[j].in[k]==2) continue; else if(data[j].in[k] != data[i].out[k]) {mark = 0; break;} } if(mark) add(i+n,j,inf); } } int bfs() { for(int i = 1; i <= t; i++) deg[i] = -1; queue<int > q; q.push(s); deg[s] = 0; while(!q.empty()) { int u = q.front(); q.pop(); //cout << "u "<< u <<endl; for(int i = h[u] ;~i; i = edge[i].next) { int v = edge[i].to,rem = edge[i].rem; if(rem && deg[v] == -1) { deg[v] = deg[u] + 1; q.push(v); } } } return deg[t] != -1; } int dfs(int u,int f) { if(u == t) return f; for(int i = cur[u] ;~i; i = edge[i].next) { cur[u] = i; int v = edge[i].to,rem = edge[i].rem,rev = edge[i].rev; if(deg[v] == deg[u]+1 && rem) { int k = dfs(v,min(f,rem)); if(!k) continue; edge[i].rem -= k; edge[rev].rem += k; return k; } } return 0; } void solve() { int flow = 0; while(bfs()) { for(int i = s; i <= t; i++) cur[i] = h[i]; for(;;) { int k = dfs(s,inf); if(k == 0) break; flow += k; } } printf("%d ",flow); int onum = 0; for(int u = n+1; u <= n*n; u++) for(int i = h[u]; ~i; i = edge[i].next) { int v = edge[i].to, rem = edge[i].rem, cap = edge[i].cap; if(cap && rem < cap && v <= n) out[onum][0] = u-n, out[onum][1] = v, out[onum++][2] = cap-rem; } printf("%d\n",onum); for(int i = 0; i < onum; i++) printf("%d %d %d\n", out[i][0] , out[i][1] , out[i][2]); } int main() { while(~scanf("%d%d",&p,&n)) { init(); for(int i = 1; i <= n; i++) { scanf("%d",&data[i].sum); for(int j = 0; j < p; j++) scanf("%d",&data[i].in[j]); for(int j = 0; j < p; j++) scanf("%d",&data[i].out[j]); } pre(); solve(); } return 0; }
