UVALive 2957 Bring Them There

Bring Them There

Time Limit: 3000ms

Memory Limit: 131072KB

This problem will be judged on UVALive. Original ID: 2957
64-bit integer IO format: %lld Java class name: Main

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

Input consists of several datasets. The first line of each dataset 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 (2N50, 1M200, 1K50, 1S, TN, 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

On the first line of the output for each dataset print L - the fewest number of days needed to deliver K supercomputers from star system S to star system T using hypertunnels. Next Llines 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, Bmeans 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

Sample Output

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

Source

Regionals 2003, Europe - Northeastern

解题：大白上面的题目，网络流拆点，有些难度，坑爹的地方在于使用dinic算法，不能继续多路增广了，一旦达到那个阈值，必须停止增广，否则，WA

输出确实巧妙狗血

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int INF = ~0U>>2;
  4 const int maxn = 5010;
  5 struct arc {
  6     int to,flow,next;
  7     arc(int x = 0,int y = 0,int z = -1) {
  8         to = x;
  9         flow = y;
 10         next = z;
 11     }
 12 } e[maxn*100];
 13 int head[maxn],d[maxn],cur[maxn],tot,S,T;
 14 void add(int u,int v,int flow) {
 15     e[tot] = arc(v,flow,head[u]);
 16     head[u] = tot++;
 17     e[tot] = arc(u,0,head[v]);
 18     head[v] = tot++;
 19 }
 20 bool bfs() {
 21     queue<int>q;
 22     memset(d,-1,sizeof d);
 23     q.push(S);
 24     d[S] = 1;
 25     while(!q.empty()) {
 26         int u = q.front();
 27         q.pop();
 28         for(int i = head[u]; ~i; i = e[i].next) {
 29             if(e[i].flow && d[e[i].to] == -1) {
 30                 d[e[i].to] = d[u] + 1;
 31                 q.push(e[i].to);
 32             }
 33         }
 34     }
 35     return d[T] > -1;
 36 }
 37 int dfs(int u,int low) {
 38     if(u == T) return low;
 39     int a,tmp = 0;
 40     for(int &i = cur[u]; ~i; i = e[i].next) {
 41         if(e[i].flow &&d[e[i].to] == d[u]+1&&(a=dfs(e[i].to,min(low,e[i].flow)))) {
 42             e[i].flow -= a;
 43             e[i^1].flow += a;
 44             low -= a;
 45             tmp += a;
 46             break;
 47         }
 48     }
 49     if(!tmp) d[u] = -1;
 50     return tmp;
 51 }
 52 int dinic(int bound,int ret = 0) {
 53     while(ret < bound && bfs()) {
 54         memcpy(cur,head,sizeof head);
 55         ret += dfs(S,INF);
 56     }
 57     return ret;
 58 }
 59 int n,m,k,s,t;
 60 int x[maxn],y[maxn];
 61 void output(int day) {
 62     int to[2000],vis[2000],s[2000],t[2000];
 63     for(int i = 1; i <= k; ++i) to[i] = S;
 64     int id = 0;
 65     for(int d = 1; d <= day; ++d) {
 66         id += (n<<1); //跳过计算机停留在某个星球上一天的边
 67         int cnt = 0;
 68         for(int i = 0; i < m; ++i) {
 69             int flow1 = e[id].flow;
 70             id += 2;
 71             int flow2 = e[id].flow;
 72             id += 2;
 73             if(flow1 && !flow2) s[cnt] = y[i], t[cnt++] = x[i];
 74             if(flow2 && !flow1) s[cnt] = x[i], t[cnt++] = y[i];
 75         }
 76         memset(vis,0,sizeof vis);
 77         printf("%d", cnt);
 78         for(int i = 0; i < cnt; ++i)
 79             for(int j = 1; j <= k; ++j)
 80                 if(s[i] == to[j] && !vis[j]) {
 81                     printf(" %d %d", j, t[i]);
 82                     to[j] = t[i];
 83                     vis[j] = 1;
 84                     break;
 85                 }
 86         printf("
");
 87     }
 88 }
 89 void solve() {
 90     int ret = 0,day = 0;
 91     while(ret < k) {
 92         ++day;
 93         for(int i = 1; i <= n; ++i)
 94             add((day - 1)*n + i,day*n + i,INF);
 95         for(int i = 0; i < m; ++i) {
 96             add(x[i] + (day - 1)*n,y[i] + day*n,1);
 97             add(y[i] + (day - 1)*n,x[i] + day*n,1);
 98         }
 99         S = s;
100         T = t + day*n;
101         ret += dinic(k - ret);
102     }
103     printf("%d
",day);
104     output(day);
105 }
106 int main() {
107     while(~scanf("%d%d%d%d%d",&n,&m,&k,&s,&t)) {
108         memset(head,-1,sizeof head);
109         for(int i = tot = 0; i < m; ++i)
110             scanf("%d%d",x + i,y + i);
111         solve();
112     }
113     return 0;
114 }

View Code