以下为提高+难度。

关于这个算法我不多做阐述，因为我说的肯定没有lrj大神说得好，大家可以看他的书–《算法竞赛入门经典》，那里有详细描述。

到了这种难度，极其建议大家去抄抄代码，过一遍手，比什么都强。

我也是这一遍抄完了，才感觉这两天的网络流明白了。

下来就是代码。

code：

//洛谷 P3381 【模板】最小费用最大流#include
     
      #define ll long longusing namespace std;const int maxn=10001,inf=0x3f3f3f3f;struct edge{    int from,to,cap,flow,cost;    edge(int u,int v,int c,int f,int d):from(u),to(v),cap(c),flow(f),cost(d){}};struct MCMF{    int n,s,t;    ll cost,flow;    vector
      
        edges;    vector
       
         G[maxn];    int a[maxn],p[maxn],d[maxn],in[maxn];    void init(int n,int s,int t){        this->n=n;        this->s=s;        this->t=t;        flow=0;        cost=0;        edges.clear();        for(int i=1;i<=n;i++){            G[i].clear();        }    }    void addedge(int x,int y,int l,int w){        edges.push_back(edge(x,y,l,0,w));        edges.push_back(edge(y,x,0,0,-w));        int m=edges.size();        G[x].push_back(m-2);        G[y].push_back(m-1);    }    bool spfa(){        memset(in,0,sizeof(in));        memset(d,0x3f,sizeof(d));        queue
        
          q;        in[s]=1;        q.push(s);        d[s]=0;        a[s]=inf;        p[s]=0;        while(!q.empty()){            int u=q.front();            q.pop();            in[u]=0;            for(int i=0;i
         
          e.flow&&d[e.to]>d[u]+e.cost){                    d[e.to]=d[u]+e.cost;                    a[e.to]=min(a[u],e.cap-e.flow);                    p[e.to]=G[u][i];                    if(!in[e.to]){                        q.push(e.to);                        in[e.to]=1;                    }                }            }        }        if(d[t]==inf){            return false;        }        flow+=a[t];        cost+=a[t]*d[t];        int x=t;        while(x!=s){            edges[p[x]].flow+=a[t];            edges[p[x]^1].flow-=a[t];            x=edges[p[x]].from;        }        return true;    }    void maxflow(){        while(spfa());    }}mcmf;int main(){    int n,m,s,t;    scanf("%d %d %d %d",&n,&m,&s,&t);    mcmf.init(n,s,t);    for(int i=1;i<=m;i++){        int x,y,l,w;        scanf("%d %d %d %d",&x,&y,&l,&w);        mcmf.addedge(x,y,l,w);    }    mcmf.maxflow();    printf("%lld %lld",mcmf.flow,mcmf.cost);    return 0;}