题目描述

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

输入格式

第一行包含四个正整数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

（BYX：最后两个点改成了1200ms）

数据规模：

对于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。

 

题解：模板最小费用最大流。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int N=100006;const int oo=0x3f3f3f3f;int n,m,s,t,ans1,ans2,cnt=1;struct node{ int to,next,w,f;}e[N];bool vis[N];int head[N],flow[N],pre[N],dis[N];void add(int x,int y,int z,int v){ cnt++; e[cnt].to=y; e[cnt].w=z; e[cnt].f=v; e[cnt].next=head[x]; head[x]=cnt; cnt++; e[cnt].to=x; e[cnt].w=0; e[cnt].f=-v; e[cnt].next=head[y]; head[y]=cnt;}queue
             
              q;bool SPFA(int s,int t){ memset(dis,oo,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0; vis[s]=1; flow[s]=oo; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].to; int f=e[i].f; if(e[i].w && dis[u]+f