I post my implementation of the Edmonds-Karp Algorithm. link to pastebin http://pastebin.com/HrxTvN4m

  1. #include <iostream>
  2. #include <climits>
  3. #define MAXN 100
  4. using namespace std;
  5. typedef struct node_t node_t;
  6. typedef struct edge_t edge_t;
  7. struct edge_t {
  8.     int cap, ni,i;
  9. };
  10. struct node_t{
  11.     int i;
  12.     edge_t edges[MAXN];
  13. };
  14. node_t nodes[MAXN];
  15. int nedges[MAXN]={0};
  16. int edmondskarp(int source, int sink, int n){
  17.     int max = 0;
  18.     while(true){
  19.         int q[MAXN]={0}, mins[MAXN]={INT_MAX}, h=0,t=0,c,i,j,min=INT_MAX;
  20.         edge_t *pre[MAXN]={NULL}, *u;
  21.         q[t++]=source;
  22.         while(t>h && pre[sink]==NULL){
  23.             c = q[h++];
  24.             for(i=0;i<n;i++) {
  25.                 if(nodes[c].edges[i].cap>0 && pre[nodes[c].edges[i].ni]==NULL){
  26.                     q[t++]=nodes[c].edges[i].ni;
  27.                     pre[nodes[c].edges[i].ni]=&nodes[c].edges[i];
  28.                     if(mins[c]>nodes[c].edges[i].cap) mins[nodes[c].edges[i].ni]=nodes[c].edges[i].cap;
  29.                     else mins[nodes[c].edges[i].ni]=mins[c];
  30.                 }
  31.             }
  32.         }
  33.         if(pre[sink]==NULL) break;
  34.         for(u=pre[sink];pre[(*u).i]!=NULL;u=pre[(*u).i]){
  35.             (*u).cap-=mins[sink];
  36.         }
  37.         max+=mins[sink];
  38.     }
  39.     return max;
  40. }
  41.  
  42. int main(){
  43.     int n, m, i, k, j, c,maxflow;
  44.     cin >> n >> m;
  45.     for(i=0;i<m;i++) {
  46.         cin >> k >> j >> c;
  47.         nodes[k].i=k;
  48.         nodes[k].edges[nedges[k]].i=k;
  49.         nodes[k].edges[nedges[k]].cap =c;
  50.         nodes[k].edges[nedges[k]].ni=j;
  51.         nedges[k]++;
  52.     }
  53.     maxflow=edmondskarp(0,n-1,n);
  54.     cout << maxflow << endl;
  55.     cin >> i;
  56.     return 0;
  57. }
Share/Bookmark a2a_linkname="Maximum Flow - Edmonds-Karp Algorithm";a2a_linkurl="http://www.studentguru.gr/blogs/ikaragkiozoglou/archive/2011/03/08/maximum-flow-edmonds-karp-algorithm.aspx";