fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define Task "A"
  3. #define up(i,a,b) for (int i = a; i <= b; i++)
  4. #define bit(x,i) ((x >> i) & 1)
  5. #define ep emplace_back
  6. using namespace std;
  7.  
  8. const int maxn = 501;
  9. vector<int> a[maxn];
  10. int n,m,s,t;
  11. int c[maxn][maxn], f[maxn][maxn];
  12. queue<int> Q;
  13. int tr[maxn];
  14. const int LIM = 2*1e9+31;
  15.  
  16. void in(){
  17.     cin >> n >> m >> s >> t;
  18.     up(i,1,n){
  19.         cin >> c[i][i+n];
  20.         a[i].ep(i+n);
  21.         a[i+n].ep(i);
  22.     }
  23.     int u,v;
  24.     up(i,1,m){
  25.         cin >> u >> v;
  26.         a[u].ep(v+n);
  27.         a[v].ep(u+n);
  28.  
  29.         a[u+n].ep(v);
  30.         a[v+n].ep(u);
  31.         c[u+n][v] = c[v+n][u] = LIM;
  32.     }
  33. }
  34.  
  35. void EdmondsKarp(int root){
  36.     Q = queue<int>{};
  37.     Q.push(root);
  38.     while (!Q.empty()){
  39.         int u = Q.front();
  40.         for (int v : a[u]){
  41.             if (!tr[v] && f[u][v] < c[u][v]){
  42.                 tr[v] = u;
  43.                 if (v == t+n) return;
  44.                 Q.push(v);
  45.             }
  46.         }
  47.         Q.pop();
  48.     }
  49. }
  50.  
  51. bool argument_path_found(){
  52.     memset(tr, 0, sizeof(tr));
  53.     tr[s] = -1;
  54.     EdmondsKarp(s);
  55.     return tr[t+n];
  56. }
  57.  
  58. void IncFlow(){
  59.     int de = LIM;
  60.     int v = t+n;
  61.     while (v != s){
  62.         int u = tr[v];
  63.         de = min(de, c[u][v] - f[u][v]);
  64.         v = u;
  65.     }
  66.  
  67.     v = t+n;
  68.     while (v != s){
  69.         int u = tr[v];
  70.         f[u][v] += de;
  71.         f[v][u] -= de;
  72.         v = u;
  73.     }
  74. }
  75.  
  76. signed main(){
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(0);
  79.     cout.tie(0);
  80.     if (fopen(Task".inp", "r")){
  81.         freopen (Task".inp", "r", stdin);
  82.         freopen (Task".out", "w", stdout);
  83.     }
  84.  
  85.     in();
  86.     while (argument_path_found()) IncFlow();
  87.  
  88.     vector<int> luu;
  89.     up(i,1,n) if (tr[i] && !tr[i+n]) luu.ep(i);
  90.  
  91.     cout << luu.size() << "\n";
  92.     for (auto x : luu) cout << x << " ";
  93. }
  94.  
Success #stdin #stdout 0.01s 5632KB
comments (?)
stdin
copy 
16 21 13 4
100 3 4 7 6 7 8 2 6 4 5 5 7 3 9 100
1 2
1 3
1 4
2 8
2 9
3 4
3 6
3 7
4 5
5 7
8 13
8 14
9 6
6 10
7 12
7 11
13 15
14 15
14 16
10 16
11 16
stdout
copy 
2
8 14
https://ideone.com/zr0Ury
language:
C++14 (gcc 8.3)
created:
4 years 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!