Min cost Max flow算法
Luogu P3381
实现思路
邻接表保存时注意：
费用具有对称性,流量具有守恒性
spfa()根据边的容量\流量\花费来找到增广路, 以及维护每点的入边pre[i],和判断是否还有增广路EK()路程:
已经通过了spfa()确定了增广路,第一次while找到增广路可以通过的最大流量,第二次while()更新网络维护maxflow和maxFlowminCost
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std
;
const int inf
= 1e9+5;
const int maxn
= 5005;
const int maxm
= 1e5+5;
struct Edge
{
int v
,c
,flow
,cost
,next
;
} edge
[maxm
];
int n
,m
,source
,sink
;
int tot
;
int head
[maxn
],dist
[maxn
],pre
[maxm
];
bool vis
[maxn
];
void addedge(int u
,int v
,int c
,int cost
) {
edge
[tot
].v
= v
; edge
[tot
].c
= c
;
edge
[tot
].cost
= cost
; edge
[tot
].flow
= 0;
edge
[tot
].next
= head
[u
]; head
[u
] = tot
++;
edge
[tot
].v
= u
; edge
[tot
].c
= 0;
edge
[tot
].cost
= -cost
; edge
[tot
].flow
= 0;
edge
[tot
].next
= head
[v
]; head
[v
] = tot
++;
}
bool
spfa(int source
,int sink
) {
queue
<int> que
;
memset(dist
,inf
,sizeof dist
);
memset(vis
, 0, sizeof vis
);
memset(pre
,-1, sizeof pre
);
dist
[source
] = 0;
vis
[source
] = 1;
que
.push(source
);
while (!que
.empty()) {
int cur
= que
.front(); que
.pop();
vis
[cur
] = 0;
for (int i
=head
[cur
]; i
!=-1; i
=edge
[i
].next
) {
int v
=edge
[i
].v
;
if (edge
[i
].c
> edge
[i
].flow
&& dist
[v
] > dist
[cur
]+edge
[i
].cost
) {
dist
[v
] = dist
[cur
] + edge
[i
].cost
;
pre
[v
] = i
;
if (!vis
[v
]) {
vis
[v
] = 1;
que
.push(v
);
}
}
}
}
if (pre
[sink
] == -1)
return 0;
return 1;
}
int EK(int source
,int sink
,int &cost
) {
int maxflow
= 0;
while (spfa(source
,sink
)) {
int delta
= inf
;
int i
= pre
[sink
];
while (i
!= -1) {
delta
= min(delta
,edge
[i
].c
-edge
[i
].flow
);
i
= pre
[edge
[i
^1].v
];
}
i
= pre
[sink
];
while (i
!= -1) {
edge
[i
].flow
+= delta
;
edge
[i
^1].flow
-= delta
;
cost
+= (delta
* edge
[i
].cost
);
i
= pre
[edge
[i
^1].v
];
}
maxflow
+= delta
;
}
return maxflow
;
}
int main() {
cin
>> n
>> m
>> source
>> sink
;
memset(head
,-1,sizeof head
);
int u
,v
,w
,f
;
for (int i
=1; i
<=m
; ++i
) {
cin
>> u
>> v
>> w
>> f
;
addedge(u
,v
,w
,f
);
}
int cost
= 0;
int maxflow
= EK(source
,sink
,cost
);
cout
<< maxflow
<< " " << cost
<< endl
;
return 0;
}
