fork download
copy 
  1. #include<bits/stdc++.h>
  2. int n,m;
  3. int adj[501][501],rg[501][501];
  4. using namespace std;
  5. bool bfs(int s,int t,int *par)
  6. {
  7.  bool vis[n];
  8.  memset(vis,0,sizeof(vis));
  9.  queue<int>q;
  10.  vis[s]=1;
  11.  q.push(s);
  12.  par[s]=-1;
  13.  while(!q.empty())
  14.  {
  15.     int u=q.front();
  16.     q.pop();
  17.     for(int v=0;v<n;v++)
  18.         {
  19.         if(vis[v] || rg[u][v]<=0) continue;
  20.         vis[v]=1;
  21.         q.push(v);
  22.         par[v]=u;
  23.     if(v==t) return true;
  24.     }
  25.  }
  26.  return false;
  27. }
  28. int ford_fulkerson(int s,int t)
  29. {
  30.  
  31. for(int i=0;i<n;i++)
  32.     for(int j=0;j<n;j++)
  33.        rg[i][j]=adj[i][j];
  34.        int par[n],maxflow=0;
  35.        while(bfs(s,t,par))
  36.        {
  37.        int res_capacity=INT_MAX;
  38.        int v=t;
  39.        while(v!=s)
  40.         {
  41.         int u=v;
  42.           res_capacity=min(res_capacity,rg[u][v]);
  43.           v=par[v];
  44.        }
  45.        v=t;
  46.        while(v!=s)
  47.        {
  48.         int u=par[v];
  49.         rg[u][v]-=res_capacity;
  50.         rg[u][v]+=res_capacity;
  51.         v=par[v];
  52.  
  53.        }
  54.        maxflow+=res_capacity;
  55.        }
  56.        return maxflow;
  57.  
  58. }
  59. int main(){
  60. cin>>n;
  61. for(int i=0;i<n;i++)
  62.     for(int j=0;j<n;j++)
  63.         cin>>adj[i][j];
  64.  
  65. int s=0,t=n-1;
  66. cout<<(ford_fulkerson(s,t));
  67.  
  68.  
  69. return 0;
  70.  
  71.  
  72.  
  73.  
  74. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VDMadS
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!