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