poj3436ACM Computer Factory(不用拆点+最大流)
题目请戳这里
题目大意：一台电脑有p个零件组成，有n个电脑组装机，每个组装机只能组装特定机器。即第i台组装机只能组装必含某些零件或者不能含有某些零件的半成品，通过这台组装机可以组装成另一台半成品/成品。每个组装机每个小时能组装的台数一定，给定n个组装机和组装条件，求每小时最多能装配多少台电脑，并输出效率最高时的一些可行方案。
题目分析：最大流。每个组装机为一个点，对于每个组装机，如果组装条件没有必须不能存在的零件，那么源点与之连一条边，边权为此组装机每小时最大组装量。如果某组装机组装成的机器为成品（每个零件都齐全了），与汇点连边，边权为此组装机每小时的工作量。然后对于每对组装机，如果i组装出的半成品符号j的组装条件，那么i与j建边，边权为i每小时的工作量。最后跑一遍最大流即可。输出方案就是在残余网络中一遍bfs，找出所有流量非0的边，输出即可。
PS：随便搜了一下，此题网上解法基本上都是人云亦云的拆点+网络流，却又讲不明白为什么要拆点。为什么要拆点？此题本来就是有向图，而且从源点建边的时候控制好流量，就不会流错的，为什么要拆点呢？
详情请见代码：
#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 55;const int M = 3000;const int inf = 0x3f3f3f3f;int p,n,num;struct node{ int to,next,c,f,pre;}arc[M];int tim[N],head[N],sta[N],que[N],cnt[N],dis[N],rpath[N];int ts[N][11],td[N][11];struct nd{ int u,v,f;}ans[M];void build(int s,int e,int cap){ arc[num].to = e; arc[num].c = cap; arc[num].f = 0; arc[num].next = head[s]; head[s] = num ++; arc[num - 1].pre = num; arc[num].pre = num - 1; arc[num].to = s; arc[num].c = arc[num].f = 0; arc[num].next = head[e]; head[e] = num ++;}bool isok(int x,int y){ int i; for(i = 1;i <= p;i ++) { if((ts[y][i] == 1 && td[x][i] != 1) || (ts[y][i] == 0 && td[x][i] != 0)) return false; } return true;}void init(){ int i,j; bool flag; memset(head,-1,sizeof(head)); num = 0; scanf("%d",&n); for(i = 1;i <= n;i ++) { flag = true; scanf("%d",&tim[i]); for(j = 1;j <= p;j ++) { scanf("%d",&ts[i][j]); if(ts[i][j] == 1) flag = false; } if(flag) build(0,i,tim[i]); flag = true; for(j = 1;j <= p;j ++) { scanf("%d",&td[i][j]); if(td[i][j] != 1) flag = false; } if(flag) build(i,n + 1,tim[i]); } for(i = 1;i <= n;i ++) { for(j = 1;j <= n;j ++) { if(i == j) continue; if(isok(i,j)) build(i,j,tim[i]); } }}void re_Bfs(){ int i,front,rear; for(i = 0;i <= n + 1;i ++) { dis[i] = n + 2; cnt[i] = 0; } front = rear = 0; que[rear ++] = n + 1; cnt[0] = 1; dis[n + 1] = 0; while(front != rear) { int u = que[front ++]; for(i = head[u];i != -1;i = arc[i].next) { if(arc[arc[i].pre].c == 0 || dis[arc[i].to] < n + 2) continue; dis[arc[i].to] = dis[u] + 1; cnt[dis[arc[i].to]] ++; que[rear ++] = arc[i].to; } }}void ISAP(){ re_Bfs(); int i,u,maxflow = 0; for(i = 0;i <= n + 1;i ++) sta[i] = head[i]; u = 0; while(dis[0] < n + 2) { if(u == n + 1) { int curflow = inf; for(i = 0;i != n + 1;i = arc[sta[i]].to) curflow = min(curflow,arc[sta[i]].c); for(i = 0;i != n + 1;i = arc[sta[i]].to) { arc[sta[i]].c -= curflow; arc[arc[sta[i]].pre].c += curflow; arc[sta[i]].f += curflow; arc[arc[sta[i]].pre].f -= curflow; } maxflow += curflow; u = 0; } for(i = sta[u];i != -1;i = arc[i].next) if(arc[i].c > 0 && dis[arc[i].to] + 1 == dis[u]) break; if(i != -1) { sta[u] = i; rpath[arc[i].to] = arc[i].pre; u = arc[i].to; } else { if((-- cnt[dis[u]]) == 0) break; sta[u] = head[u]; int Min = n + 2; for(i = sta[u];i != -1;i = arc[i].next) if(arc[i].c > 0) Min = min(Min,dis[arc[i].to]); dis[u] = Min + 1; cnt[dis[u]] ++; if(u != 0) u = arc[rpath[u]].to; } } printf("%d ",maxflow);}void solve(){ ISAP(); int ansnum = 0; int i,front,rear; front = rear = 0; memset(cnt,0,sizeof(cnt)); cnt[0] = 1; for(i = head[0];i != -1;i = arc[i].next) if(arc[i].f > 0) { que[rear ++] = arc[i].to; cnt[arc[i].to] = 1; } while(front != rear) { int u = que[front ++]; for(i = head[u];i != -1;i = arc[i].next) { if(arc[i].f > 0 && arc[i].to != n + 1) { ans[ansnum].u = u; ans[ansnum].v = arc[i].to; ans[ansnum ++].f = arc[i].f; if(cnt[arc[i].to] == 0) { que[rear ++] = arc[i].to; cnt[arc[i].to] = 1; } } } } printf("%d\n",ansnum); for(i = 0;i < ansnum;i ++) printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].f);}int main(){ while(scanf("%d",&p) != EOF) { init(); solve(); } return 0;}//180K16MS