7 int N=INT_MAX,N1,N2,TOT=0;
21 static void get(const char *s,int *vp)
25 if (tty) { fputs(s,stdout); fputs(": ",stdout); fflush(stdout); }
26 i=scanf("%d",vp); assert(i==1);
27 assert(*vp>=1 && *vp<=N);
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) {
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;
62 for (i=1;i<=N;i++) V[i].path=NULL;
65 for (p=V+N1;p && p!=V+N2;p=p->path)
66 for (e=p->e;e;e=e->next)
68 (( e==e->forw && e->f<e->c )
69 ||( e!=e->forw && e->forw->f>0 ))) {
70 *patht=e->d; patht=&e->d->path;
75 for (p2=p;(e=p->back);p=e->s) {
76 d=(e==e->forw ? e->c-e->f : e->f);
80 assert(p==V+N1); assert(diff>0 || diff<INT_MAX);
82 for (p=p2;(e=p->back);p=e->s)
83 if (e==e->forw) e->f+=diff;
85 if (p2->back->forw==p2->back) TOT+=diff;
89 printf("Total network flow is: %d\n",TOT);