【网络流24题】No. 17 运输问题（费用流）

98 阅读 0 评论 65 点赞

我是靠谱客的博主动听大山，最近开发中收集的这篇文章主要介绍【网络流24题】No. 17 运输问题（费用流），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题意】

　　W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有ai 个单位的货物；第 j 个零售商店需要b j 个单位的货物。

货物供需平衡，即SIGMA(A)=SIGMA(B)。

从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 cij 。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

输入文件示例
input.txt
2 3
220 280
170 120 210
77 39 105
150 186 122

输出文件示例
output.txt
48500
69140

【分析】

　　很裸的费用流吧。而且是二分图。。


1 #include<cstdio>

2 #include<cstdlib>

3 #include<cstring>

4 #include<iostream>

5 #include<algorithm>

6 #include<queue>

7 #include<cmath>

8 using namespace std;

9 #define Maxn 1010
 10 #define INF 0xfffffff
 11
 12 struct node
 13 {
 14
int x,y,f,o,c,next;
 15 }t[Maxn*Maxn],tt[Maxn*Maxn];int len;
 16 int first[Maxn];
 17
 18 int mymin(int x,int y) {return x<y?x:y;}
 19 int mymax(int x,int y) {return x>y?x:y;}
 20
 21 void ins(int x,int y,int f,int c)
 22 {
 23
t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c;
 24
t[len].next=first[x];first[x]=len;t[len].o=len+1;
 25
t[++len].x=y;t[len].y=x;t[len].f=0;t[len].c=-c;
 26
t[len].next=first[y];first[y]=len;t[len].o=len-1;
 27 }
 28
 29 int st,ed;
 30 queue<int > q;
 31 int dis[Maxn],pre[Maxn],flow[Maxn];
 32 bool inq[Maxn];
 33 bool bfs()
 34 {
 35
while(!q.empty()) q.pop();
 36
memset(dis,63,sizeof(dis));
 37
memset(inq,0,sizeof(inq));
 38
q.push(st);dis[st]=0;flow[st]=INF;inq[st]=1;
 39
while(!q.empty())
 40 
{
 41
int x=q.front();
 42
for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 43 
{
 44
int y=t[i].y;
 45
if(dis[y]>dis[x]+t[i].c)
 46 
{
 47
dis[y]=dis[x]+t[i].c;
 48
pre[y]=i;
 49
flow[y]=mymin(flow[x],t[i].f);
 50
if(!inq[y])
 51 
{
 52
inq[y]=1;
 53 
q.push(y);
 54 
}
 55 
}
 56 
}
 57
inq[x]=0;q.pop();
 58 
}
 59
if(dis[ed]>=INF-100000) return 0;
 60
return 1;
 61 }
 62
 63 void output()
 64 {
 65
for(int i=1;i<=len;i+=2)
 66
printf("%d->%d %d %dn",t[i].x,t[i].y,t[i].f,t[i].c);
 67
printf("n");
 68 }
 69
 70 int max_flow()
 71 {
 72
int ans=0,sum=0;
 73
while(bfs())
 74 
{
 75
sum+=dis[ed]*flow[ed];
 76
ans+=flow[ed];
 77
int now=ed;
 78
while(now!=st)
 79 
{
 80
t[pre[now]].f-=flow[ed];
 81
t[t[pre[now]].o].f+=flow[ed];
 82
now=t[pre[now]].x;
 83 
}
 84 
}
 85
return sum;
 86 }
 87
 88 int m,n;
 89
 90 void init()
 91 {
 92
scanf("%d%d",&m,&n);
 93
st=m+n+1;ed=st+1;
 94
len=0;
 95
memset(first,0,sizeof(first));
 96
for(int i=1;i<=m;i++)
 97 
{
 98
int x;
 99
scanf("%d",&x);
100
ins(st,i,x,0);
101 
}
102
for(int i=1;i<=n;i++)
103 
{
104
int x;
105
scanf("%d",&x);
106
ins(i+m,ed,x,0);
107 
}
108
for(int i=1;i<=m;i++)
109
for(int j=1;j<=n;j++)
110 
{
111
int x;
112
scanf("%d",&x);
113
ins(i,j+m,INF,x);
114 
}
115 }
116
117 int main()
118 {
119 
init();
120
// output();
121
// return 0;
122
for(int i=1;i<=len;i++) tt[i]=t[i];
123
int ans;
124
ans=max_flow();
125
printf("%dn",ans);
126
for(int i=1;i<=len;i++) t[i]=tt[i];
127
for(int i=1;i<=len;i++) t[i].c=-t[i].c;
128
ans=max_flow();
129
printf("%dn",-ans);
130
return 0;
131 }