Topic analysis
It can be seen that this problem should be solved by network flow, but if only network flow is used, "each tunnel takes a day to pass" can not be handled.
In this problem, we notice that whether each computer can move is related to the current state of the graph, and the current state of the graph is related to the parameter "time", so we should consider the influence of time when building the graph, in other words, build a hierarchical graph. Assuming that a total of \ (t \) days have been transported, we can divide each point \ (U \) into \ (T + 1 \) points \ (u_0 \), \ (u_2 \), \ (u_3 \),..., \ (u_T \), \ (u_i \) represents the node \ (U \) on the \ (I \) day, and use the method of \ (u_i = u + in \) for specific implementation.
For an undirected edge \ ((u, v) \), we connect the edge with the capacity of \ (1 \) from \ (u u I \) to \ (v {I + 1} \), and the edge with the capacity of \ (1 \) from \ (v U I \) to \ (U {I + 1} \), which means that the spacecraft can spend a day from \ (U \) to \ (v \) or from \ (v \) to \ (U \). At the same time, for each node \ (U \), we connect the side with positive infinite capacity from \ (u_i \) to \ (u_{i + 1} \), indicating that the spacecraft can stay in place.
First of all, you can think of dichotomy \ (T \). However, it is also possible to build drawings layer by layer (increase \ (T \) by \ (1 \) each time), After each layer is built, run the maximum flow from \ (s_0 \) to \ (t_T \) on the last residual network until the maximum flow reaches \ (k \). (stop immediately when \ (k \) is reached, which can be achieved by limiting the initial flow during expansion.)
Another thorny problem is how to output the scheme. In fact, the information about the movement of all computers on day \ (I \) is stored in the layer \ (I \). If the edge from \ (u_i \) to \ (v_{i + 1} \) is full, it means that a computer moves from \ (U \) to \ (V \) on day \ (i + 1 \). (since all computers are indistinguishable from each other, the edges from \ (u_i \) to \ (v_ {i + 1} \) and from \ (v_i \) to \ (u_{i + 1} \) are full and can be regarded as offsetting each other.)
Therefore, we can record all "movement events" first, and then for each movement from \ ((u, v) \), we can find a computer whose current location is \ (u \), change its location to \ (v \) and output it. Of course, because a computer can only be moved once a day, we must record whether each computer has been moved that day. If it has been moved, it will not be moved again.
code implementation
#include<bits/stdc++.h>
using namespace std;
struct Edge {
int u, v;
};
const int MAXN = 5000 + 5;
const int MAXM = 200000 + 5;
const int MAXK = 50 + 5;
const int INF = INT_MAX;
Edge e[MAXM];
pair<int, int> mov[MAXM];
queue<int> q;
int pos[MAXK];
bool blk[MAXK];
int head[MAXN], to[MAXM], nxt[MAXM], flow[MAXM], cap[MAXM];
int tot = 1;
int dep[MAXN], cur[MAXN];
int n, m, k, s, T, t;
int cnt, ans;
void init() {
memset(head, 0, sizeof(head));
tot = 1;
}
void addEdge(int u, int v, int c, int f) {
tot++;
to[tot] = v;
nxt[tot] = head[u];
flow[tot] = f;
cap[tot] = c;
head[u] = tot;
}
bool bfs() {
memset(dep, 0, sizeof(dep));
while(!q.empty()) q.pop();
q.push(s);
dep[s] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; i != 0; i = nxt[i]) {
if(cap[i] > flow[i] && dep[to[i]] == 0) {
dep[to[i]] = dep[u] + 1;
q.push(to[i]);
if(to[i] == t) return true;
}
}
}
return false;
}
int dinic(int u, int limit) {
if(u == t || limit == 0) {
return limit;
}
int rest = limit;
for(int& i = cur[u]; i != 0; i = nxt[i]) {
if(cap[i] > flow[i] && dep[to[i]] == dep[u] + 1) {
int k = dinic(to[i], min(rest, cap[i] - flow[i]));
if(k == 0) {
dep[to[i]] = 0;
}
flow[i] += k;
flow[i ^ 1] -= k;
rest -= k;
if(rest == 0) break;
}
}
return limit - rest;
}
int maxflow(int limit) {
int res = 0;
while(bfs()) {
memcpy(cur, head, sizeof(head));
res += dinic(s, limit - res); //Flow limit, make sure the flow is exactly $k$
if(res == limit) {
break;
}
}
return res;
}
void output() {
for(int i = 1; i <= k; i++) {
pos[i] = s;
}
int now = 2;
for(int i = 1; i <= cnt; i++) {
memset(blk, 0, sizeof(blk));
ans = 0;
for(int j = 1; j <= m; j++) {
if(flow[now] == 1 && flow[now + 2] == 0) {
mov[++ans] = make_pair(e[j].u, e[j].v);
}
if(flow[now] == 0 && flow[now + 2] == 1) {
mov[++ans] = make_pair(e[j].v, e[j].u);
}
now += 4;
}
now += n * 2;
printf("%d", ans);
for(int j = 1; j <= ans; j++) {
for(int p = 1; p <= k; p++) {
if(blk[p]) {
continue;
}
if(pos[p] == mov[j].first) {
pos[p] = mov[j].second;
printf(" %d %d", p, pos[p]);
blk[p] = true;
break;
}
}
}
printf("\n");
}
}
int main() {
while(scanf("%d%d%d%d%d", &n, &m, &k, &s, &T) == 5) {
init();
for(int i = 1; i <= m; i++) {
scanf("%d%d", &e[i].u, &e[i].v);
}
cnt = 0;
int sum = 0;
while(sum < k) {
cnt++;
t = cnt * n + T;
for(int i = 1; i <= m; i++) {
addEdge(e[i].u + (cnt - 1) * n, e[i].v + cnt * n, 1, 0);
addEdge(e[i].v + cnt * n, e[i].u + (cnt - 1) * n, 0, 0);
addEdge(e[i].v + (cnt - 1) * n, e[i].u + cnt * n, 1, 0);
addEdge(e[i].u + cnt * n, e[i].v + (cnt - 1) * n, 0, 0);
}
for(int i = 1; i <= n; i++) {
addEdge(i + (cnt - 1) * n, i + cnt * n, INF, 0);
addEdge(i + cnt * n, i + (cnt - 1) * n, 0, 0);
}
sum += maxflow(k - sum);
}
printf("%d\n", cnt);
output();
}
return 0;
}