0%

ZOJ3362 Beer Problem,有重边的最大流最小费用

挺不错的一条最大流最小费用题,因为有重边,所以我们用邻接表来做,详情请看代码中的注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/*******************************************************************************
# Author : Neo Fung
# Email : neosfung@gmail.com
# Last modified: 2011-10-10 19:47
# Filename: ZOJ3362 Beer Problem.cpp
# Description :
******************************************************************************/
// #include "stdafx.h"
// #define DEBUG
//

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <memory.h>
#include <limits.h>
#include <vector>
#include <stack>
#include <math.h>
#define MAX 120
using namespace std;

struct NODE
{
int to,cap,value,next;
}node[MAX*MAX];

int city[MAX];
int cou,n,m;

void init()
{
memset(city,-1,sizeof(city));
cou=0;
}

void addEdge(int from,int to,int cap,int value)
{
node[cou].to=to;
node[cou].cap=cap;
node[cou].value=value;
node[cou].next=city[from];
city[from]=cou++;

node[cou].to=from;
node[cou].cap=0;
node[cou].value=-value;
node[cou].next=city[to];
city[to]=cou++;
}

int EKwithSPFA(int source,int target)
{
int value[MAX],pre_v[MAX],pre_e[MAX],instack[MAX]; //pre_v记录本节点的上一个节点,pre_e记录的是上一个节点到本节点的边的编号
int ans=0;
stack<int> mstack;

while(1)
{
//不断进行SPFA,找出残余路径中费用最小的路径
for(int i=source;i<=target;++i)
value[i]=INT_MIN;
value[source]=0;
memset(instack,0,sizeof(instack));
memset(pre_v,-1,sizeof(pre_v)); //全部指向无效节点
instack[source]=1;
mstack.push(source); //我们用栈而不是队列可以减少时间
//spfa根据每条边的value求最短路
while(!mstack.empty())
{
int u=mstack.top();
mstack.pop();
instack[u]=0;
for(int i=city[u];i!=-1;i=node[i].next)
{
int v=node[i].to;
if(node[i].cap>0 && value[v]<value[u]+node[i].value) //判断边还有没有余下空间,以及到底v节点后的利润能否增加
{
value[v]=value[u]+node[i].value;
pre_v[v]=u;
pre_e[v]=i;
if(!instack[v])
{
mstack.push(v);
instack[v]=1;
}
}
}
}
if(value[target]<=0) //如果到了终点,利润是负数,则代表可以走的边都走完了,退出
break;
int a=INT_MAX;
for(int u=target;u!=source;u=pre_v[u])
{
int e=pre_e[u];
a=min(a,node[e].cap); //找出这条通路的瓶颈
}
for(int u=target;u!=source;u=pre_v[u])
{
int e=pre_e[u];
node[e].cap-=a;
node[e^1].cap+=a; //更新这条通路上所有边的容量,异或求反向边,偶数和1异或代表加1,奇数和1异或代表减1
}
ans+=value[target]*a; //瓶颈乘以终点的费用就是新增的费用
}
return ans;
}

int main(void)
{
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif

int from,to,cap,value;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=2;i<=n;++i)
{
scanf("%d",&value);
addEdge(i,n+1,INT_MAX,value); //这里我们规定从目标城市卖出去的啤酒的价格是正数
}
for(int i=0;i<m;++i)
{
scanf("%d%d%d%d",&from,&to,&cap,&value);
addEdge(from,to,cap,-value); //这里我们规定运输成本是负数
addEdge(to,from,cap,-value); //不要忘了是双向边
}
int ans=EKwithSPFA(1,n+1);
printf("%d\n",ans);
}

return 0;
}