费用流

最小费用最大流模板,洛谷P3381

下面是我自己的写的邻接矩阵,容易懂,但是超时

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+5,maxm=100000+5,inf=1000000000;
int w[maxn][maxn],f[maxn][maxn];
int n,m,s,t,e=0,ans1,csum1;
int vis[maxn],dist[maxn],pre[maxn];
bool spfa(){
memset(vis,-1,sizeof(vis));
for(int i=1;i<=n;i++)dist[i]=inf;
queue<int>q;
dist[s]=0;vis[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop(); vis[u]=-1;
for(int i=1;i<=n;i++)
if(w[u][i] && dist[i]>dist[u]+f[u][i]){
dist[i]=dist[u]+f[u][i];
pre[i]=u;
if(vis[i]<0){
q.push(i); vis[i]=0;
}
}
}
if(dist[t]==inf)return 0;
ans1=inf;
int k=t;
while(k!=s){
ans1=min(ans1,w[pre[k]][k]);
k=pre[k];
}
k=t;
csum1=0;
while(k!=s){
csum1+=f[pre[k]][k]*ans1;
w[pre[k]][k]-=ans1;
w[k][pre[k]]+=ans1;
k=pre[k];
}
return 1;
}
int main(){
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,uw,uc;
scanf("%d%d%d%d",&u,&v,&uw,&uc);
w[u][v]=uw;
f[u][v]=uc;
f[v][u]=-uc;
}
int ans=0,csum=0;
while(spfa()){
ans+=ans1;
csum+=csum1;
}
printf("%d %d\n",ans,csum);
return 0;
}

下面是CZY大佬写的链式前向星,AC了

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
#define REP(i, s, e) for(register int i = s; i <= e ;i++)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 5, maxm = 50000 + 5, inf((((1 << 30) - 1) << 1) + 1);
int bg[maxn], ne[maxm << 1], to[maxm << 1], w[maxm << 1], cost[maxm << 1], e = 1;

inline void add(int x, int y, int z, int c)
{
e++;
to[e] = y;
ne[e] = bg[x];
bg[x] = e;
w[e] = z;
cost[e] = c;
}

int n, m, S, T;

int max_flow, min_cost;

queue <int> q;
bool vis[maxn];
int dis[maxn], pre[maxn], Max[maxn];
inline bool spfa()
{
memset(vis, 0, sizeof(vis));
REP(i, 1, n) dis[i] = inf;
dis[S] = 0;
while (!q.empty()) q.pop();
q.push(S);
Max[S] = inf;

while (!q.empty())
{
register int x = q.front();
q.pop();
vis[x] = 0;
for (register int i = bg[x]; i ; i = ne[i])
if (w[i] > 0 && dis[to[i]] > dis[x] + cost[i])
{
dis[to[i]] = dis[x] + cost[i];
pre[to[i]] = i;
Max[to[i]] = min(Max[x], w[i]);
if (!vis[to[i]])
{
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return dis[T] != inf;
}

inline void update()
{
int x = T;
while (x != S)
{
w[pre[x]] -= Max[T];
w[pre[x] ^ 1] += Max[T];
x = to[pre[x] ^ 1];
}
max_flow += Max[T];
min_cost += Max[T] * dis[T];
}

int main(){
cin >> n >> m >> S >> T;
while (m--)
{
int x, y, z, c;
scanf("%d%d%d%d", &x, &y, &z, &c);
add(x, y, z, c);
add(y, x, 0, -c);
}
while (spfa()) update();
cout << max_flow << ' ' << min_cost;
return 0;
}

撒花、✿✿ヽ(°▽°)ノ✿

文章目录
  1. 1. 最小费用最大流模板,洛谷P3381