project/FordFulk/FordFulk/FordFulk.c

   1 #include <stdio.h>
   2 #include <assert.h>
   3 #include <stdlib.h>
   4 #include <limits.h>
   5 #include <unistd.h>
   6
   7 int N=INT_MAX,N1,N2,TOT=0;
   8 char tty;
   9
  10 struct E {
  11         struct E *next,*forw;
  12         struct V *s,*d;
  13         int f,c;
  14         };
  15
  16 struct V {
  17         struct V *path;
  18         struct E *e,*back;
  19         } *V,**patht;
  20
  21 static void get(const char *s,int *vp)
  22 {
  23 int i;
  24
  25         if (tty) { fputs(s,stdout); fputs(": ",stdout); fflush(stdout); }
  26         i=scanf("%d",vp); assert(i==1);
  27         assert(*vp>=1 && *vp<=N);
  28 }
  29
  30 int main(void)
  31 {
  32 int i,V1,V2,C,diff;
  33
  34         tty=!!ttyname(STDIN_FILENO);
  35         get("Number of cities",&N ); assert(N>=2);
  36         get("Starting city #" ,&N1);
  37         get("Ending   city #" ,&N2);
  38         if (tty) puts("Write <start city> <end city> <capacity> triples. Finish by EOF");
  39         V=calloc(N+1,sizeof(*V)); assert(V);
  40         while ((i=scanf("%d%d%d",&V1,&V2,&C))==3) {
  41 struct E *e,*e0,*e1;
  42
  43                 assert(V1>=1 && V1<=N && V2>=1 && V2<=N && V1!=V2 && C>0);
  44                 for (e=V[V1].e;e;e=e->next) assert(!(e->forw==e && e->d==V+V2));
  45                 e0=malloc(sizeof(*e0)); assert(e0);
  46                 e1=malloc(sizeof(*e1)); assert(e1);
  47                 e0->next=V[V1].e; V[V1].e=e0;
  48                 e1->next=V[V2].e; V[V2].e=e1;
  49                 e0->s=V+V1; e0->d=V+V2;
  50                 e1->s=V+V2; e1->d=V+V1;
  51                 e0->forw=e1->forw=e0;
  52                 e0->f=0; e0->c=C;
  53                 e1->f=e1->c=-1;
  54                 }
  55         assert(i<=0);
  56
  57         for (;;) {
  58 struct V *p,*p2;
  59 struct E *e;
  60 int d;
  61
  62                 for (i=1;i<=N;i++) V[i].path=NULL;
  63                 patht=&V[N1].path;
  64                 V[N1].back=NULL;
  65                 for (p=V+N1;p && p!=V+N2;p=p->path)
  66                         for (e=p->e;e;e=e->next)
  67                                 if (!e->d->path &&
  68                                         (( e==e->forw && e->f<e->c    )
  69                                  ||( e!=e->forw && e->forw->f>0 ))) {
  70                                         *patht=e->d; patht=&e->d->path;
  71                                         e->d->back=e;
  72                                         }
  73                 if (!p) break;
  74                 diff=INT_MAX;
  75                 for (p2=p;(e=p->back);p=e->s) {
  76                         d=(e==e->forw ? e->c-e->f : e->f);
  77                         assert(d>0);
  78                         if (d<diff) diff=d;
  79                         }
  80                 assert(p==V+N1); assert(diff>0 || diff<INT_MAX);
  81
  82                 for (p=p2;(e=p->back);p=e->s)
  83                         if (e==e->forw) e->f+=diff;
  84                         else            e->f-=diff;
  85                 if (p2->back->forw==p2->back) TOT+=diff;
  86                 else                          TOT-=diff;
  87                 assert(TOT>0);
  88                 }
  89         printf("Total network flow is: %d\n",TOT);
  90         return(EXIT_SUCCESS);
  91 }