uva 1324 Bring Them There

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

题目大意：宇宙中有n个星球，你的任务是用最短的时间把k个超级计算机从S星运到T星。没个超级计算机需要一整艘飞船来运输。行星之间有m条双向隧道，每条隧道需要一天时间来通过，且不能有两艘飞船同时使用同一条隧道。隧道不会连接两个相同的星球，且每一对行星之间最多只有一条隧道。

解题思路：没什么思路，看了别人的题解，觉得他的方法非常之巧妙，我再深入的理解一下，再回来补题解。

#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; }