如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。

输入输出格式

输入格式：

 

第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），单位流量的费用为fi。

 

输出格式：

 

一行，包含两个整数，依次为最大流量和在最大流量情况下的最小费用。

 

输入输出样例

输入样例#1：

4 5 4 34 2 30 24 3 20 32 3 20 12 1 30 91 3 40 5

输出样例#1：

50 280

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=1000，M<=1000

对于100%的数据：N<=5000，M<=50000

样例说明：

如图，最优方案如下：

第一条流为4-->3，流量为20，费用为3*20=60。

第二条流为4-->2-->3，流量为20，费用为（2+1）*20=60。

第三条流为4-->2-->1-->3，流量为10，费用为（2+9+5）*10=160。

故最大流量为50，在此状况下最小费用为60+60+160=280。

故输出50 280。

思路：费用流

因为要注意费用的问题，所以用SPFA找费用最小的增广路，不要用Dijkstra（因为有负边权）（然而一般情况下SPFA更好写，所以这个警告是废话）；

然后增广ap()。

几个注意的地方：

反边费用为其对应边的相反数；

队列首尾指针记得清零；（RE了50%左右）

有一种常（la）数（ji）级优化技巧叫先留个坑，反边随用随建。（优化程度达不到O（）*0.5，但是够用，而且很好实现）；

代码实现：

1 #include
      
        2 #include
       
         3 #define maxn 5010 4 #define maxm 100010 5 #define maxt 2139062143 6 int n,m,s,t,nflow,nfee,flow,fee; 7 int a,b,c,d; 8 long long la,lb; 9 int h[maxn],hs=1;10 struct edge{
    int s,n,w,f;}e[maxm];11 int w[maxn];12 int p[maxn][2];13 int q[maxm],head,tail;14 int min(int x,int y){
    return x
        
         tail){20         a=q[tail++];21         for(int i=h[a];i;i=e[i].n)22         if(e[i].w){23             la=e[i].f,lb=w[a],la+=lb,lb=w[e[i].s];24             if(la
        
       
      

代码重构：

struct换为数组；（更快）

函数重构；（更优美）

结果：916ms

1 #include
     
       2 #include
      
        3 const int maxn=1e4+10; 4 const int maxm=1e5+10; 5 const int maxt=2139062143; 6 inline int min_(int x,int y){
   return x
       
        tail){29             a=q[tail++],v[a]=0;30             for(int i=h[a];i;i=e_n[i])31             if(0ll+e_f[i]+w[a]
       
      
     

题目来源：洛谷