fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxN = 501, maxM = 1001;
  4. const int INF = 0x3f3f3f3f;
  5. int N, M, K, p[maxN], d[maxN];
  6. bool inq[maxN], vis[maxM];
  7. vector<int> path, G[maxN];
  8.  
  9. struct Edge {
  10.     int u, v, r, c;
  11. } edges[maxM], redges[maxM];
  12.  
  13. void bellman_ford(){
  14.     fill(inq+1, inq+N+1, false);
  15.     fill(d+1, d+N+1, INF);
  16.     fill(p+1, p+N+1, 0);
  17.  
  18.     queue<int> Q;
  19.     Q.push(1);
  20.     d[1] = 0;
  21.     inq[1] = true;
  22.     while(!Q.empty()){
  23.         int u = Q.front(); Q.pop();
  24.         inq[u] = false;
  25.  
  26.         for(int i : G[u]){
  27.             Edge e = (i < 0 ? redges[-i] : edges[i]);
  28.             if(e.r > 0 && d[e.v] > d[u] + e.c){
  29.                 d[e.v] = d[u] + e.c;
  30.                 p[e.v] = i;
  31.                 if(!inq[e.v]){
  32.                     inq[e.v] = true;
  33.                     Q.push(e.v);
  34.                 }
  35.             }
  36.         }
  37.     }
  38. }
  39.  
  40. int minimum_cost_flow(){
  41.     int flow = 0, cost = 0;
  42.     while(flow < K){
  43.         bellman_ford();
  44.         if(d[N] == INF) break;
  45.  
  46.         int aug = K-flow;
  47.         int u = N;
  48.         while(u != 1){
  49.             Edge e = (p[u] < 0 ? redges[-p[u]] : edges[p[u]]);
  50.             aug = min(aug, e.r);
  51.             u = e.u;
  52.         }
  53.  
  54.         flow += aug;
  55.         cost += aug * d[N];
  56.         u = N;
  57.         while(u != 1){
  58.             if(p[u] < 0){
  59.                 redges[-p[u]].r -= aug;
  60.                 edges[-p[u]].r += aug;
  61.             } else {
  62.                 redges[p[u]].r += aug;
  63.                 edges[p[u]].r -= aug;
  64.             }
  65.             u = (p[u] < 0 ? redges[-p[u]].u : edges[p[u]].u);
  66.         }
  67.     }
  68.     return (flow < K ? -1 : cost);
  69. }
  70.  
  71. void dfs(int u = 1){
  72.     path.push_back(u);
  73.     if(u == N)  return;
  74.     for(int i : G[u]){
  75.         if(i > 0 && edges[i].r == 0 && !vis[i]){
  76.             vis[i] = true;
  77.             dfs(edges[i].v);
  78.             return;
  79.         }
  80.     }
  81. }
  82.  
  83. int main(){
  84.     scanf("%d %d %d", &N, &M, &K);
  85.     for(int i = 1, u, v; i <= M; i++){
  86.         scanf("%d %d", &u, &v);
  87.         G[u].push_back(i);
  88.         G[v].push_back(-i);
  89.         edges[i] = {u, v, 1, 1};
  90.         redges[i] = {v, u, 0, -1};
  91.     }
  92.  
  93.     int minCoins = minimum_cost_flow();
  94.     if(minCoins == -1){
  95.         printf("-1\n");
  96.         return 0;
  97.     }
  98.  
  99.     printf("%d\n", minCoins);
  100.     for(int i = 0; i < K; i++){
  101.         path.clear();
  102.         dfs();
  103.  
  104.         int sz = (int) path.size();
  105.         printf("%d\n", sz);
  106.         for(int j = 0; j < sz; j++)
  107.             printf("%d%c", path[j], (" \n")[j==sz-1]);
  108.     }
  109. }
  110.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/nL1HYf
language:
C++14 (gcc 8.3)
created:
177 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!