#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();
} 

评论