UVA 1324 LA 2957 网络流(拆点+输出解)
poj也有这题，但数据很弱，建议去UVa上去交
链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36127
题意：n个点m个双向边，每天每条边最大只能用一次(要么u->v运一个，要么v->u运一个)，把k台电脑从S都运到T至少需要几天，并输出解。(n <= 50,m <= 200, k <= 50)，保证有解。
思路：答案一定<=100，所以枚举天数，每次增加一天并尝试将增广使其总流量为k，直到增广满足条件为止，然后根据残余网络中的流量流向情况输出解。
如何建图：抓住每条边每天只能流一次，所以我们必须把这些边按天数拆，具体实现是拆点的。把每个点拆成u0，u1....ui，表示第i天电脑在u节点，对于原边<u，v> 连 所以 u(i)->v(i+1)，然后u(i)->u(i+1)连边(表示原地不动)。
具体实现：每当当前的总流量< k时，就把天数加一，再在图中新加n个点(表示新的天数)并添加所需要的边。
可以将S的第0天的点看成源点(因为没有连向它的边)。 假如当前进行到了第t天，那么我把点T的第t天节点看成汇点，增广使其总流量为k(不到k就增广到最接近k)。 直到总流量为k时就停止。
输出解：模拟， 对于每一天分别输出解，pos[i]记录第i台电脑当前天在原图的节点编号， 对于这天，枚举新图第一天的所有边，有流量流过就让某个i走一下，并保存一下，然后在处理一下，具体看代码吧。
注意点：1. 在跑最网络流时，不是把流量增广到最大，而是尽可能的增广到k
2. 输出解的时候假如有U1--->V2 U2--->V1 两条边都有流量，不满足题意，但可以看成两台电脑都原地不动，自然这种情况这两条边就相互抵消了，不用记录下来。 (具体实现：建边的时候可以建在一起，然后方便一起枚举这2条边)
总结：1.建边的时候稍微把边排版了一下，方便了枚举，让输出解变得很容易。
2.在原有的图中选S，T
3.每次增加天数，把节点增加到数组的后面，然后在同一个图上进行增广，
而不是每次重新建图再增广
//同时枚举2条边避免上面第2个注意点int f1 = edge[idx^1].c; idx += 2;int f2 = edge[idx^1].c; idx += 2;if(f1 && !f2) a.push_back(u[i]), b.push_back(v[i]);if(!f1 && f2) a.push_back(v[i]), b.push_back(u[i]);}printf("%d", a.size());for(i = 0; i < a.size(); i++)for(j = 0; j < k; j++)if(!vis[j] && a[i] == pos[j]) {printf(" %d %d", j+1, b[i]);pos[j] = b[i];vis[j] = 1;break;} puts("");}}return 0;}