【费用流】【Next Array】费用流模板(spfa版)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【费用流】【Next Array】费用流模板(spfa版)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2885字，纯文字阅读大概需要5分钟。
内容图文
一、非结构体版
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 #include<queue>
5usingnamespace std;
6#define MAXN 501
7#define MAXM 50001
8#define INF 2147483647
9int S,T;
10int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Array11bool inq[MAXN];
12int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;
13 queue<int>q;
14void Init_MCMF(){memset(first,-1,sizeof(first));en=0;}
15void AddEdge(constint &U,constint &V,constint &W,constint &C)
16{
17 u[en]=U; v[en]=V; cap[en]=W; cost[en]=C;
18 next[en]=first[U];
19 first[U]=en++;
20 u[en]=V; v[en]=U; cost[en]=-C;
21 next[en]=first[V];
22 first[V]=en++;
23}
24bool Spfa(int &Flow,int &Cost)
25{
26 memset(d,0x7f,sizeof(d));
27 memset(inq,0,sizeof(inq));
28 d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);
29while(!q.empty())
30 {
31int U=q.front(); q.pop(); inq[U]=0;
32for(int i=first[U];i!=-1;i=next[i])
33if(cap[i] && d[v[i]]>d[U]+cost[i])
34 {
35 d[v[i]]=d[U]+cost[i];
36 p[v[i]]=i;
37 a[v[i]]=min(a[U],cap[i]);
38if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}
39 }
40 }
41if(d[T]>2000000000) return0;
42 Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;
43while(U!=S)
44 {
45 cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];
46 U=u[p[U]];
47 }
48return1;
49}
50int Mincost()
51{
52int Flow=0,Cost=0;
53while(Spfa(Flow,Cost));
54return Cost;
55 }
二、结构体版
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 #include<queue>
5usingnamespace std;
6#define MAXN 5001
7#define MAXM 100001
8#define INF 2147483647
9int S,T,n,m;
10int en,first[MAXN];
11struct NextArray{int u,v,cap,cost,next;}NA[MAXM];
12bool inq[MAXN];
13int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;
14 queue<int>q;
15void Init_MCMF(){en=0;memset(first,-1,sizeof(first));}
16void AddEdge(constint &U,constint &V,constint &W,constint &C)
17{
18 NA[en].u=U; NA[en].v=V; NA[en].cap=W; NA[en].cost=C;
19 NA[en].next=first[U]; first[U]=en++;
20 NA[en].u=V; NA[en].v=U; NA[en].cost=-C;
21 NA[en].next=first[V]; first[V]=en++;
22}
23bool Spfa(int &Flow,int &Cost)
24{
25 memset(d,0x7f,sizeof(d));
26 memset(inq,0,sizeof(inq));
27 d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);
28while(!q.empty())
29 {
30int U=q.front(); q.pop(); inq[U]=0;
31for(int i=first[U];i!=-1;i=NA[i].next)
32if(NA[i].cap && d[NA[i].v]>d[U]+NA[i].cost)
33 {
34 d[NA[i].v]=d[U]+NA[i].cost;
35 p[NA[i].v]=i;
36 a[NA[i].v]=min(a[U],NA[i].cap);
37if(!inq[NA[i].v]) {q.push(NA[i].v); inq[NA[i].v]=1;}
38 }
39 }
40if(d[T]>2000000000) return0;
41 Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;
42while(U!=S)
43 {
44 NA[p[U]].cap-=a[T]; NA[p[U]^1].cap+=a[T];
45 U=NA[p[U]].u;
46 }
47return1;
48}
49int Mincost()
50{
51int Flow=0,Cost=0;
52while(Spfa(Flow,Cost));
53return Cost;
54 }
原文：http://www.cnblogs.com/autsky-jadek/p/4149096.html
内容总结
以上是互联网集市为您收集整理的【费用流】【Next Array】费用流模板(spfa版)全部内容，希望文章能够帮你解决【费用流】【Next Array】费用流模板(spfa版)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】