首页 > 代码库 > 洛谷 3381 【模板】最小费用最大流
洛谷 3381 【模板】最小费用最大流
https://www.luogu.org/problem/show?pid=3381
题目描述
如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。
输入输出格式
输入格式:
第一行包含四个正整数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。
反边随用随加
只需要在spfa的时候记录路径最小流量
在给每条边减流量的时候新建反边即可
#include<cstdio>#include<queue>#define N 50010using namespace std;queue<int>q;int n,m,tot;int src,dec;int to[N*2],from[N*2],nextt[N*2],front[N],cap[N*2],cost[N*2],dis[N],pre[N*2];int minn[N];bool v[N];int sum_cost,sum_flow;void add(int u,int v,int f,int w){ to[++tot]=v;from[tot]=u;nextt[tot]=front[u];front[u]=tot;cap[tot]=f;cost[tot]=w;}bool spfa(){ for(int i=1;i<=n;i++) dis[i]=0x7fffffff,minn[i]=0x7fffffff; q.push(src);v[src]=true;dis[src]=0; while(!q.empty()) { int now=q.front(); q.pop();v[now]=false; for(int i=front[now];i;i=nextt[i]) { if(dis[to[i]]>dis[now]+cost[i]&&cap[i]>0) { dis[to[i]]=dis[now]+cost[i]; minn[to[i]]=min(minn[now],cap[i]); pre[to[i]]=i; if(!v[to[i]]) { q.push(to[i]); v[to[i]]=true; } } } } return dis[dec]!=0x7fffffff;}int main(){ scanf("%d%d%d%d",&n,&m,&src,&dec); int u,v,w,f; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&u,&v,&w,&f); add(u,v,w,f); } while(spfa()) { if(sum_cost+minn[dec]*dis[dec]>=0) { sum_cost+=dis[dec]*minn[dec]; sum_flow+=minn[dec]; for(int i=pre[dec];i;i=pre[from[i]]) { cap[i]-=minn[dec]; add(to[i],from[i],minn[dec],-cost[i]); } } else { sum_flow-=int(sum_cost/dis[dec]); break; } } printf("%d %d",sum_flow,sum_cost);}
洛谷 3381 【模板】最小费用最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。