Description
By the year 3141, the human civilization has spread all over the galaxy. The special hypertunnels are used to travel from one star system to another. To use the hypertunnel, you fly to a special location near the source star using your spaceship, activate the hyperjumper, fly through the hypertunnel, get out near your destination star and fly to the planet you need. The whole process takes exactly one day. A small drawback of the system is that for each tunnel every day only one spaceship can travel using this tunnel.
You are working in the transportation department of the “Intergalaxy Business Machines” company. This morning your boss has assigned a new task to you. To run the programming contest IBM needs to deliver K supercomputers from Earth where the company headquarters are located to the planet Eisiem. Since supercomputers are very large, one needs the whole spaceship to carry each supercomputer. You are asked to find a plan to deliver the supercomputers that takes as few days as possible. Since IBM is a very powerful corporation, you may assume that any time you need some tunnel for hyperjump, it is at your service. However, you still can use each tunnel only once a day.
Input Specification
The input consists of several test cases. The first line of each case contains N — the number of star systems in the galaxy, M — the number of tunnels, K — the number of supercomputers to be delivered, S — the number of the solar system (the system where planet Earth is) and T — the number of the star system where planet Eisiem is (2 <= N <= 50, 1 <= M <= 200, 1 <= K <= 50, 1 <= S, T <= N , S T ).
Next M lines contain two different integer numbers each and describe tunnels. For each tunnel the numbers of star systems that it connects are given. The tunnel can be traveled in both directions, but remember that each day only one ship can travel through it, in particular, two ships cannot simultaneously travel through the same tunnel in opposite directions. No tunnel connects a star to itself and any two stars are connected by at most one tunnel.
Output Specification
For each test case print in the first line L — the fewest number of days needed to deliver K supercomputers from star system S to star system T using hypertunnels. Next L lines must describe the process. Each line must start with Ci — the number of ships that travel from one system to another this day. Ci pairs of integer numbers must follow, pair A, B means that the ship number A travels from its current star system to star system B. It is guaranteed that there is a way to travel from star system S to star system T .
Sample Input
6 7 4 1 6
1 2
2 3
3 5
5 6
1 4
4 6
4 3
Output for the Sample Input
4
2 1 2 2 4
3 1 3 2 6 3 4
3 1 5 3 6 4 4
2 1 6 4 6
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 5005;
const int M = 100005;
const int INF = 0x3f3f3f3f;
int n, m, k, s, t, Day;
int u[N], v[N];
struct Dinic{
int ec, head[N], first[N], que[N], lev[N];
int Next[M], to[M], v[M];
void init() {
ec = 0;
memset(first, -1, sizeof(first));
}
void addEdge(int a,int b,int c) {
to[ec] = b;
v[ec] = c;
Next[ec] = first[a];
first[a] = ec++;
to[ec] = a;
v[ec] = 0;
Next[ec] = first[b];
first[b] = ec++;
}
int BFS() {
int kid, now, f = 0, r = 1, i;
memset(lev, 0, sizeof(lev));
que[0] = s, lev[s] = 1;
while (f < r) {
now = que[f++];
for (i = first[now]; i != -1; i = Next[i]) {
kid = to[i];
if (!lev[kid] && v[i]) {
lev[kid] = lev[now] + 1;
if (kid == t) return 1;
que[r++] = kid;
}
}
}
return 0;
}
int DFS(int now, int sum) {
int kid, flow, rt = 0;
if (now == t || sum == 0) return sum;
for (int i = head[now]; i != -1 && rt < sum; i = Next[i]) {
head[now] = i;
kid = to[i];
if (lev[kid] == lev[now] + 1 && v[i]) {
flow = DFS(kid, min(sum - rt, v[i]));
if (flow) {
v[i] -= flow;
v[i^1] += flow;
rt += flow;
} else lev[kid] = -1;
}
}
return rt;
}
int dinic(int num, int need) {
int ans = 0;
while (BFS()) {
for (int i = 0; i <= num; i++) {
head[i] = first[i];
}
ans += DFS(s, need - ans);
if (ans == need) return ans;
}
return ans;
}
}din;
void input() {
for (int i = 0; i < m; i++) {
scanf(%d %d, &u[i], &v[i]);
}
}
void solve() {
int sum = 0;
Day = 1;
int tt = t;
while (sum < k) {
for (int i = 1; i <= n; i++) {
din.addEdge((Day - 1) * n + i, Day * n + i, INF);
// printf({%d %d INF}
, (Day - 1) * n + i, Day * n + i);
}
// puts();
for (int i = 0; i < m; i++) {
din.addEdge((Day - 1) * n + u[i], Day * n + v[i], 1);
din.addEdge((Day - 1) * n + v[i], Day * n + u[i], 1);
printf(%d %d 1
, (Day - 1) * n + u[i], Day * n + v[i]);
printf(%d %d 1
, (Day - 1) * n + v[i], Day * n + u[i]);
}puts();
t = tt + Day * n;
sum += din.dinic(Day * n + n, k - sum);
if (sum == k) break;
Day++;
}
printf(%d
, Day);
int idx = 0;
vector location(k, s);
for(int d = 1; d <= Day; d++){
idx += n * 2;
vector moved(k, 0);
vector a, b;
for(int i = 0; i < m; i++){
int f1= din.v[idx^1];
idx += 2;
int f2= din.v[idx^1];
idx += 2;
if(f1 && !f2) {
a.push_back(u[i]);
b.push_back(v[i]);
}
if(f2 && !f1) {
a.push_back(v[i]);
b.push_back(u[i]);
}
}
printf(%d, (int)a.size());
for(int i = 0; i < a.size(); i++){
for(int j = 0; j < k; j++) {
if(!moved[j] && location[j] == a[i]){
moved[j] = 1;
printf( %d %d, j + 1, b[i]);
location[j] = b[i];
break;
}
}
}puts();
}
}
int main() {
while (scanf(%d %d %d %d %d, &n, &m, &k, &s, &t) == 5) {
din.init();
input();
solve();
}
return 0;
}
