题目描述
如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。
输入格式
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），单位流量的费用为fi。
输出格式
一行，包含两个整数，依次为最大流量和在最大流量情况下的最小费用。
输入输出样例
输入 #1
4 5 4 3 4 2 30 2 4 3 20 3 2 3 20 1 2 1 30 9 1 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<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> 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<int>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<dis[v]){ dis[v]=dis[u]+f; pre[v]=i; flow[v]=min(flow[u],e[i].w); if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(dis[t]==oo) return 0; else return 1; } void dfs(int s,int t){ int x=t; while(x!=s){ int i=pre[x]; e[i].w-=flow[t]; e[i^1].w+=flow[t]; x=e[i^1].to; } ans1+=flow[t]; ans2+=flow[t]*dis[t]; } int main(){ freopen("3381.in","r",stdin); freopen("33811.out","w",stdout); memset(head,-1,sizeof(head)); scanf("%d %d %d %d",&n,&m,&s,&t); int x,y,z,v; for(int i=1;i<=m;i++){ scanf("%d %d %d %d",&x,&y,&z,&v); add(x,y,z,v); } while(SPFA(s,t)) dfs(s,t); //cout<<6666; printf("%d %d ",ans1,ans2); return 0; }