Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Maximum Flow- Edmonds-Karp Algorithm
- // by Iraklis Karagkiozoglou <[email protected]>
- #include <iostream>
- #include <climits>
- #define MAXN 100
- using namespace std;
- typedef struct node_t node_t;
- typedef struct edge_t edge_t;
- struct edge_t {
- int cap, ni,i;
- };
- struct node_t{
- int i;
- edge_t edges[MAXN];
- };
- node_t nodes[MAXN];
- int nedges[MAXN]={0};
- int edmondskarp(int source, int sink, int n){
- int max = 0;
- while(true){
- int q[MAXN]={0}, mins[MAXN]={INT_MAX}, h=0,t=0,c,i,j,min=INT_MAX;
- edge_t *pre[MAXN]={NULL}, *u;
- q[t++]=source;
- while(t>h && pre[sink]==NULL){
- c = q[h++];
- for(i=0;i<n;i++) {
- if(nodes[c].edges[i].cap>0 && pre[nodes[c].edges[i].ni]==NULL){
- q[t++]=nodes[c].edges[i].ni;
- pre[nodes[c].edges[i].ni]=&nodes[c].edges[i];
- if(mins[c]>nodes[c].edges[i].cap) mins[nodes[c].edges[i].ni]=nodes[c].edges[i].cap;
- else mins[nodes[c].edges[i].ni]=mins[c];
- }
- }
- }
- if(pre[sink]==NULL) break;
- u=pre[sink];
- while(u!=NULL) {
- (*u).cap-=mins[sink];
- u=pre[(*u).i];
- }
- max+=mins[sink];
- }
- return max;
- }
- int main(){
- int n, m, i, k, j, c,maxflow;
- cin >> n >> m;
- for(i=0;i<m;i++) {
- cin >> k >> j >> c;
- nodes[k].i=k;
- nodes[k].edges[nedges[k]].i=k;
- nodes[k].edges[nedges[k]].cap =c;
- nodes[k].edges[nedges[k]].ni=j;
- nedges[k]++;
- }
- maxflow=edmondskarp(0,n-1,n);
- cout << maxflow << endl;
- cin >> i;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement