fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mxn = 501;
  4. int rGraph[mxn][mxn];
  5. int orGraph[mxn][mxn];
  6. int parent[mxn];
  7. int n, m;
  8.  
  9. bool bfs(int s, int t)
  10. {
  11.     bool visited[mxn] = {};
  12.     queue<int> q;
  13.  
  14.     q.push(s);
  15.     visited[s] = true;
  16.     parent[s] = -1;
  17.  
  18.     while(!q.empty())
  19.     {
  20.         int u = q.front();
  21.         q.pop();
  22.  
  23.         for(int v = 0; v < n; v++)
  24.         {
  25.             if(rGraph[u][v] > 0 && !visited[v])
  26.             {
  27.                 parent[v] = u;
  28.                 visited[v] = true;
  29.  
  30.                 if(v == t)
  31.                     return true;
  32.  
  33.                 q.push(v);
  34.             }
  35.         }
  36.     }
  37.     return false;
  38. }
  39. long long ff(int s, int t)
  40. {
  41.     long long maxflow = 0;
  42.  
  43.     while(bfs(s, t))
  44.     {
  45.         long long pathflow = LLONG_MAX;
  46.  
  47.         for(int v = t; v != s; v = parent[v])
  48.         {
  49.             int u = parent[v];
  50.             pathflow = min(pathflow, (long long)rGraph[u][v]);
  51.         }
  52.         for(int v = t; v != s; v = parent[v])
  53.         {
  54.             int u = parent[v];
  55.             rGraph[u][v] -= pathflow;
  56.             rGraph[v][u] += pathflow;
  57.         }
  58.         maxflow += pathflow;
  59.     }
  60.     return maxflow;
  61. }
  62. void minc(int s)
  63. {
  64.     bool visited[mxn] = {};
  65.     queue<int> q;
  66.     q.push(s);
  67.     visited[s] = true;
  68.  
  69.     while(!q.empty())
  70.     {
  71.         int u = q.front();
  72.         q.pop();
  73.  
  74.         for(int v = 0; v < n; v++)
  75.         {
  76.             if(rGraph[u][v] > 0 && !visited[v])
  77.             {
  78.                 visited[v] = true;
  79.                 q.push(v);
  80.             }
  81.         }
  82.     }
  83.     for(int u = 0; u < n; u++)
  84.     {
  85.         for(int v = 0; v < n; v++)
  86.         {
  87.             if(visited[u] && !visited[v]  &&  orGraph[u][v] > 0)
  88.             {
  89.                 cout << u << " " << v << endl;
  90.             }
  91.         }
  92.     }
  93. }
  94. int main()
  95. {
  96.     int s,t;
  97.     cin >> n >> m >> s>> t;
  98.     memset(orGraph, 0, sizeof(orGraph));
  99.     memset(rGraph, 0, sizeof(rGraph));
  100.     for(int i = 0; i < m; i++)
  101.     {
  102.         int u, v, w;
  103.         cin >> u >> v >> w;
  104.         orGraph[u][v] = w;
  105.          rGraph[u][v] = w;
  106.     }
  107.     minc(s+1);
  108.      cout<< ff(s, t);
  109.     return 0;
  110. }
  111. /*
  112. 6 10 0 5
  113. 0 1 16
  114. 0 2 13
  115. 1 2 10
  116. 1 3 12
  117. 2 1 4
  118. 2 4 14
  119. 3 2 9
  120. 3 5 20
  121. 4 3 7
  122. 4 5 4
  123. */
  124.  
Success #stdin #stdout 0.01s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/twzlYh
language:
C++ (gcc 8.3)
created:
1 day 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!