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.每次增加天数，把节点增加到数组的后面，然后在同一个图上进行增广，
而不是每次重新建图再增广
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 5010;
const int inf = 1e9;
int n, m, k, S, T;
struct Edges {
int v, c, next;
Edges(int v, int c, int next) :
v(v), c(c), next(next) {
}
Edges() {
}
} edge[10000007];
int head[maxn], E;
void add(int s, int t, int c) {
edge[E] = Edges(t, c, head[s]);
head[s] = E++;
edge[E] = Edges(s, 0, head[t]);
head[t] = E++;
}
void init() {
memset(head, -1, sizeof(head));
E = 0;
}
int gap[maxn], dis[maxn], pre[maxn], cur[maxn];
int sap(int s, int t, int n, int lim) {// s 源点，t汇点，n顶点总数, 限制最大增广的流量
int i;
for(i = 0; i <= n; i++) {
dis[i] = gap[i] = 0;
cur[i] = head[i];
}
gap[0] = n;
int u = pre[s] = s, maxf = 0, aug = lim, v;
while(dis[s] < n) {
loop: for(i = cur[u]; ~i; i = edge[i].next) {
v = edge[i].v;
if(edge[i].c && dis[u] == dis[v] + 1) {
aug = min(aug, edge[i].c);
pre[v] = u;
cur[u] = i;
u = v;
if(u == t) {
while(u != s) {
u = pre[u];
edge[cur[u]].c -= aug;
edge[cur[u] ^ 1].c += aug;
}
maxf += aug;
lim -= aug;
aug = lim;
if(!lim) return maxf;
}
goto loop;
}
}
int d = n;
for(i = head[u]; ~i; i = edge[i].next) {
v = edge[i].v;
if(edge[i].c && dis[v] < d) {
d = dis[v];
cur[u] = i;
}
}
if(!(--gap[dis[u]]))
break;
++gap[dis[u] = d + 1];
u = pre[u];
}
return maxf;
}
//*************************************
int u[203], v[203];
int ans;
void solve() {
int i, j, maxf = 0;
ans = 0;
init();
while(maxf < k) {
ans++;
for(i = 0; i < n; i++)
add((ans-1)*n+i, ans*n+i, inf);
for(i = 0; i < m; i++) {
add((ans-1)*n+u[i]-1, ans*n+v[i]-1, 1);
add((ans-1)*n+v[i]-1, ans*n+u[i]-1, 1);
}
maxf += sap(S-1, T+ans*n-1, (ans+1)*n, k-maxf);
}
printf("%d\n", ans);
}
int main() {
int i, j;
while( ~scanf("%d%d%d%d%d", &n, &m, &k, &S, &T)) {
for(i = 0; i < m; i++) scanf("%d%d", &u[i], &v[i]);
solve();
vector <int> pos(k, S);
int idx = 0;
for(int d = 1; d <= ans; d++) {
idx += (n<<1);
vector <int> a;
vector <int> b;
vector <bool> vis(k, 0);
for(i = 0; i < m; i++) {
//同时枚举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;
}