首页 > 代码库 > P3381 【模板】最小费用最大流
P3381 【模板】最小费用最大流
P3381 【模板】最小费用最大流
题目描述
如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。
输入输出格式
输入格式：
第一行包含四个正整数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。
code
pre记录的是边，不是点
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #include<cstring> 5 6 using namespace std; 7 8 const int INF = 0x7fffffff; 9 const int MAXN = 10010;10 struct Edge{11 int from,to,nxt,flow,cost;12 Edge(){}13 Edge(int a,int b,int c,int d,int e) {from=a,to=b,nxt=c,flow=d,cost=e;}14 }e[100100];15 int dis[MAXN],head[MAXN],pre[MAXN];16 bool vis[MAXN];17 int n,m,s,t,tot=1,flw,cost,ans1,ans2;18 queue<int>q;19 20 int read()21 {22 int x = 0,f = 1;char ch = getchar();23 while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘)f=-1; ch = getchar();}24 while (ch>=‘0‘&&ch<=‘9‘) x = x*10+ch-‘0‘, ch = getchar();25 return x*f;26 }27 void add_edge(int u,int v,int w,int c) 28 {29 e[++tot] = Edge(u,v,head[u],w,c);30 head[u] = tot;31 e[++tot] = Edge(v,u,head[v],0,-c);32 head[v] = tot;33 }34 bool spfa()35 {36 memset(vis,false,sizeof(vis));37 memset(pre,0,sizeof(pre));38 for (int i=1; i<=n; ++i) dis[i] = INF;39 dis[s] = 0,vis[s] = true,pre[s] = 0;40 q.push(s);41 while (!q.empty())42 {43 int u = q.front();q.pop();44 for (int i=head[u]; i; i=e[i].nxt)45 {46 int v = e[i].to;47 if (dis[v]>dis[u]+e[i].cost&&e[i].flow>0)48 {49 dis[v] = dis[u]+e[i].cost;50 pre[v] = i;51 if (!vis[v])52 {53 vis[v] = true;54 q.push(v);55 }56 }57 }58 vis[u] = false;59 }60 if (dis[t]!=INF) return 1;61 return 0;62 }63 void flow()64 {65 int mn = INF;66 for (int i=t; i!=s; i=e[pre[i]].from)67 mn = min(e[pre[i]].flow,mn);68 for (int i=t; i!=s; i=e[pre[i]].from)69 {70 e[pre[i]].flow -= mn;71 e[pre[i]^1].flow += mn;72 ans2 += e[pre[i]].cost*mn;73 }74 ans1 += mn;75 }76 int main()77 {78 n = read(),m = read(),s = read(),t = read();79 for (int a,b,c,d,i=1; i<=m; ++i)80 {81 a = read(),b = read(),c = read(),d = read();82 add_edge(a,b,c,d);83 }84 while (spfa()) flow();85 printf("%d %d",ans1,ans2);86 return 0;87 }
P3381 【模板】最小费用最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。