netstream.cpp

会的人并不很多的网络流算法源程序

#include<stdio.h>
#include<stdlib.h>
const int maxn=1000;
const int maxint=32767;
struct nbour{
       int k,f,c,w;
       struct nbour *next,*g;};
struct wtype{
       int p,d,t;
       struct nbour *w;};
int n,m,stt,trm;
struct nbour *nbs[maxn];
struct wtype pth[maxn];
void insertg(int u,int v,int c,int w){
     struct nbour *x,*p;
     x=(struct nbour*)malloc(sizeof(struct nbour));
     x->k=v;x->f=0;x->c=c; x->w=w;
     x->next=nbs[u];nbs[u]=x;
     p=(struct nbour*)malloc(sizeof(struct nbour));
     p->k=u;p->f=0;p->c=0;p->w=-w;
     p->next=nbs[v];nbs[v]=p;
     x->g=p;p->g=x;}    
void ford(){
     int f;
     int u,d;
     struct nbour *x;
     do{
        for(u=0;u<maxn;u++){
            pth[u].d=maxint;
            pth[u].p=0;
            pth[u].t=maxint;
            pth[u].w=NULL;}
        pth[stt].d=maxint; pth[stt].p=stt;
        pth[stt].t=0;
        do{
          f=0;
          for(u=1;u<n;u++) {
           x=nbs[u]; 
           while(x!=NULL){printf("%d--->%d  %d\n",x->k,x->g->k,x->c);
             d=x->c-x->f;
             if(d>0&&pth[u].t<maxint&&(pth[x->k].t>pth[u].t+x->w)){
             f=1;
               
               pth[x->k].t=pth[u].t+x->w;
               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;}}
              }while(f); 
                 
        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 ans(){
     
     int i,tot=0,cos=0;
     struct nbour *x;
     for(i=1;i<=n;i++){
       x=nbs[i];
     while(x!=NULL){
       if(x->f>0) printf("%d--->%d,%d\n",i,x->k,x->f);
                  if(i==1&&x->f>0) tot+=x->f;
                  x=x->next;}}
     printf("!%d\n",tot);}
void ans2(){
     int i,tot=0;
     struct nbour *x;
     for(i=1;i<=n;i++){
       x=nbs[i];
     while(x!=NULL){
       printf("%d--->%d,%d,%d\n",i,x->k,x->f,x->w);
                  
                  x=x->next;}}
   }
                                    
main(){
       int i,u,v,c,w;       
       FILE *fpr,*fpw;
       fpr=fopen("power.in2","r");
       fpw=fopen("power.out","w");
       fscanf(fpr,"%d %d %d",&n,&stt,&trm);
       for(u=0;u<=n;u++) nbs[u]=NULL;
       fscanf(fpr,"%d",&m);
       for(i=0;i<m;i++)
       {fscanf(fpr,"%d %d %d %d",&u,&v,&c,&w);
       insertg(u,v,c,w);}
       fclose(fpr);
       ford();
       ans();
       while(1);}