#include<iostream.h> #include<stdio.h> const maxn=1000; typedef struct Nbour {     int k;     int f,c;     Nbour *next,*g; }Nbour,*Link; typedef struct Wtype {     int p,d;     Nbour *w; }Wtype; int N,stt,trm; Link  Nbs[maxn]; Wtype Pth[maxn]; void Insert(int u,int v,int c) {     Link x;     x=Nbs[u];     while(x!=NULL&&x.k!=v)     x=x.next;     if(x!=NULL)     x.c=c;     else     {         x.k=v;         x.c=c;         x.f=0;         x.next=Nbs[u];         Nbs[u]=x;         x.g.k=u;         x.g.c=0;         x.g.f=0;         x.g.g=x;         x.g.next=Nbs[v];         Nbs[v]=x.g;     } } void Init() {     int u,v,c;     cin>>N>>stt>>trm;     for(u=1;u<N;u++)     Nbs[u]=NULL;     while(cin>>u>>v>>c)     {         insert(u,v,c);     } } void Ford() {     int Q[maxn];     int op,c1,u,d;     Link x;     do     {         fillchar(Pth,sizeof(Pth),0);         Pth[stt].d=32767;Pth[stt].p=stt;         c1=0;op=1;Q[op]=stt;         while(c1<op&&Pth[trm].p==0)         {             c1++;             u=Q[c1];             x=Nbs[u];             while(x!=NULL)             {                 d=x.c-x.f;                 if(Pth[x.k].p==0&&d>0)                 {                     op++;                     Q[op]=x.k;                     Pth[x.k].p=u;                     Pth[x.k].w=x;                     if(Pth[u].d<d)                     {                         Pth[x.k].d=Pth[u].d;                     }                     else Pth[x.k].d=d;                 }                 x=x.next;             }             if(Pth[trm].p!=0)             {                 u=trm;                 d=Pth[u].d;                 do                 {                     Pth[u].w.f=Pth[u].w.f+d;                     Pth[u].w.g.f=-Pth[u].w.f;                     u=Pth[u].p;                 }while(u==stt);             }         }         }while(Pth[trm].p==0); } void Answer() {     int i,tot;     Link x;     tot=0;     for(i=1;i<N;i++)     {         x=Nbs[i];         while(x!=NULL)         {             if(x.f>0)             {                 cout<<i<<' '<<x.k<<' '<<x.f<<endl;             }             if(i==1&&x.f>0)             {                 tot+=x.f;             }             x=x.next;         }     }     cout<<"************************** tot= "<<tot<<endl; }                                                                            int main() {     Init();     Ford();     Answer(); } 

评论