Advertisement
ikar

Maximum FLow Edmonds-Karp

Mar 8th, 2011
3,003
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. // Maximum Flow- Edmonds-Karp Algorithm
  2. // by Iraklis Karagkiozoglou <[email protected]>
  3. #include <iostream>
  4. #include <climits>
  5. #define MAXN 100
  6. using namespace std;
  7. typedef struct node_t node_t;
  8. typedef struct edge_t edge_t;
  9. struct edge_t {
  10.     int cap, ni,i;
  11. };
  12. struct node_t{
  13.     int i;
  14.     edge_t edges[MAXN];
  15. };
  16. node_t nodes[MAXN];
  17. int nedges[MAXN]={0};
  18. int edmondskarp(int source, int sink, int n){
  19.     int max = 0;
  20.     while(true){
  21.         int q[MAXN]={0}, mins[MAXN]={INT_MAX}, h=0,t=0,c,i,j,min=INT_MAX;
  22.         edge_t *pre[MAXN]={NULL}, *u;
  23.         q[t++]=source;
  24.         while(t>h && pre[sink]==NULL){
  25.             c = q[h++];
  26.             for(i=0;i<n;i++) {
  27.                 if(nodes[c].edges[i].cap>0 && pre[nodes[c].edges[i].ni]==NULL){
  28.                     q[t++]=nodes[c].edges[i].ni;
  29.                     pre[nodes[c].edges[i].ni]=&nodes[c].edges[i];
  30.                     if(mins[c]>nodes[c].edges[i].cap) mins[nodes[c].edges[i].ni]=nodes[c].edges[i].cap;
  31.                     else mins[nodes[c].edges[i].ni]=mins[c];
  32.                 }
  33.             }
  34.         }
  35.         if(pre[sink]==NULL) break;
  36.     u=pre[sink];
  37.     while(u!=NULL) {
  38.                 (*u).cap-=mins[sink];
  39.         u=pre[(*u).i];
  40.     }
  41.         max+=mins[sink];
  42.     }
  43.     return max;
  44. }
  45.  
  46. int main(){
  47.     int n, m, i, k, j, c,maxflow;
  48.     cin >> n >> m;
  49.     for(i=0;i<m;i++) {
  50.         cin >> k >> j >> c;
  51.         nodes[k].i=k;
  52.         nodes[k].edges[nedges[k]].i=k;
  53.         nodes[k].edges[nedges[k]].cap =c;
  54.         nodes[k].edges[nedges[k]].ni=j;
  55.         nedges[k]++;
  56.     }
  57.     maxflow=edmondskarp(0,n-1,n);
  58.     cout << maxflow << endl;
  59.     cin >> i;
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement