最大流问题
给出起点、终点、边最大能传递的值，问从起点到终点最多能传多少
- 阻塞流：不能再给终点增加值的流（最大流就是一种阻塞流）
- 传统算法：新建一个剩余量的图，找路径、减去最小值、删路径，重复直到为阻塞流（不一定为最优解）
Ford-Fulkerson算法(复杂度O(fm)，没什么用，过不了模板题)
相对于传统算法，它加入了一步建立反向边的步骤使得它可以"反悔"
1.找路径
2.减去最小值并建立反向的最小值边
3.重复
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans = 0;
const int MAXN = 201,MAXM = 5e3 + 10;
struct edge{
ll v,val,i;
edge* nex;
}ed[MAXM*2];
int ptop;
edge* head[MAXN];
void add(int u,int v,ll val){
ed[ptop].i = ptop;
ed[ptop].v = v;
ed[ptop].nex = head[u];
ed[ptop].val = val;
head[u] = &ed[ptop];
ptop++;
ed[ptop].v = u;
ed[ptop].i = ptop;
ed[ptop].nex = head[v];
ed[ptop].val = 0;
head[v] = &ed[ptop];
ptop++;
}
int s,t;
int ask[MAXM*2],use[MAXN];
bool find(int u){
if(u == t)
return 1;
edge* p = head[u];
for(edge* p = head[u];p != NULL;p = p -> nex){
int v = p -> v;
if(use[v] || p -> val == 0)
continue;
else{
use[v] = 1;
ask[++ptop] = p -> i;
if(find(v)) return 1;
ptop--;
}
}
return 0;
}
bool bfs(){
ptop = 0;
memset(use,0,sizeof(use));
use[s] = 1;
if(!find(s))
return 0;
ll mi = (ll)1 << 50;
for(int i = 1;i <= ptop;i++){
mi = min(mi,ed[ask[i]].val);
}
for(int i = 1;i <= ptop;i++){
ed[ask[i]].val -= mi;
ed[ask[i]^1].val += mi;
}
ans += mi;
return 1;
}
int main()
{
int n,m;cin >> n >> m >> s >> t;
for(int i = 1;i <= m;i++){
ll u,v,val;cin >> u >> v >> val;
add(u,v,val);
}
while(bfs());
cout << ans;
}
Edmonds-Karp算法(用最短路找边，时间复杂度为O(\(m^2n\)))(SAP算法)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans = 0;
const int MAXN = 201,MAXM = 5e3 + 10;
struct edge{
ll u,v,val,i;
edge* nex;
}ed[MAXM*2];
int ptop = 2;
edge* head[MAXN];
void add(int u,int v,ll val){
ed[ptop].i = ptop;
ed[ptop].v = v;
ed[ptop].u = u;
ed[ptop].nex = head[u];
ed[ptop].val = val;
head[u] = &ed[ptop];
ptop++;
ed[ptop].v = u;
ed[ptop].u = v;
ed[ptop].i = ptop;
ed[ptop].nex = head[v];
ed[ptop].val = 0;
head[v] = &ed[ptop];
ptop++;
}
int s,t;
int pre[MAXN*2],use[MAXN];
bool find(){
queue<int> qu;qu.push(s);
while(!qu.empty()){
int x = qu.front();
qu.pop();
for(edge* p = head[x];p != NULL;p = p -> nex){
int v = p -> v;
if(use[v] || p -> val == 0)
continue;
pre[v] = p -> i;
use[v] = 1;
if(v == t)
return 1;
qu.push(v);
}
}
return 0;
}
bool bfs(){
ptop = 0;
memset(use,0,sizeof(use));
use[s] = 1;
if(!find())
return 0;
ll mi = (ll)1 << 50;
for(int i = pre[t];i != 0;i = pre[ed[i].u]){
mi = min(mi,ed[i].val);
}
for(int i = pre[t];i != 0;i = pre[ed[i].u]){
ed[i].val -= mi;
ed[i^1].val += mi;
}
ans += mi;
return 1;
}
int main()
{
int n,m;cin >> n >> m >> s >> t;
for(int i = 1;i <= m;i++){
ll u,v,val;cin >> u >> v >> val;
add(u,v,val);
}
while(bfs());
cout << ans;
}
Dinic算法
- level-up图：就是分层图，起点开始，终点结束，中间分层
- Edmonds-Karp算法每次只解决一条边，效率较低，Dinic算法通过level-up图算一个图的阻塞流，效率更高
- BFS找level-up图思路：记录深度，最后看终点有没有被标记深度即可
- DFS找阻塞流：每次只找深度加1的点，深入DFS并传递边的最小值，返回分配的流，让这条边减去返回值，继续找，直到找完或者没有流可以继续了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int MAXN = 201,MAXM = 5e3 + 10;
struct edge{
int v;
ll w;
edge* nex;
int i;
}ed[MAXM*2];
edge* head[MAXN];
int ptop = 0;
void add(int u,int v,ll w){
ed[ptop].w = w;
ed[ptop].v = v;
ed[ptop].nex = head[u];
head[u] = &ed[ptop];
ed[ptop].i = ptop;
ptop++;
ed[ptop].w = 0;
ed[ptop].v = u;
ed[ptop].nex = head[v];
head[v] = &ed[ptop];//构造反向边
ed[ptop].i = ptop;
ptop++;
}
int n,m,s,t;
int d[MAXN];//记录深度
bool bfs(){//构造levelup图
queue<int> qu;
memset(d,-1,sizeof(d));
d[s] = 0;
qu.push(s);//放入起点
while(!qu.empty()){
int u = qu.front();
qu.pop();
edge* p = head[u];
while(p != NULL){
int v = p -> v;
if(p -> w && d[v] == -1){//存在且还没加入图
d[v] = d[u] + 1;
qu.push(v);
}
p = p -> nex;
}
}
if(d[t] == -1)//到不了终点
return 0;
else
return 1;
}
ll dfs(int u,ll flow){
if(u == t)
return flow;
edge* p = head[u];
ll use = 0;
while(p != NULL){
int v = p -> v;
if(d[v] == d[u] + 1 && p -> w){
ll tem = dfs(v,min(flow,p -> w));
flow -= tem;
ed[p -> i].w -= tem;
ed[(p -> i) ^ 1].w += tem;
use += tem;
if(flow == 0)
break;
}
p = p -> nex;
}
if(use == 0) d[u] = -1;
return use;
}
ll dinic(){
ll ans = 0;
while(bfs()){
ans += dfs(s,inf);
}
return ans;
}
int main()
{
cin >> n >> m >> s >> t;
for(int i = 1;i <= m;i++){
int u,v,w;cin >> u >> v >> w;
add(u,v,w);
}
cout << dinic();
}
ISAP算法
最小割等价于最大流问题
- 因为所有流都要经过割，因此所有流都大于等于割，那么最大的流就等价于最小的割
- 随便用一个最大流算法处理图，从起点出发将所有找到的点加入S集合，另外的为T集合，这样就找到最小割了(不唯一)
EK(SPFA版)费用流
-
费用流：最大流中费用最小的
-
EK算法每次都找一条可行路径，那么只要一直找费用最小的可行路径即可
-
每次都找一条费用最小的路径，反向边的费用是正向边的负权值
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10,M = 5e5 + 10,INF = 0x7f7f7f7f;
int n,m,s,t,ans1,ans2;
struct edge{
int v,flow,cost,i;
edge* nex;
}ed[M];
int ptop = 0;
edge* head[N];
void add(int u,int v,int flow,int cost){
ed[ptop].v = v;
ed[ptop].flow = flow;
ed[ptop].cost = cost;
ed[ptop].i = ptop;
ed[ptop].nex = head[u];
head[u] = &ed[ptop];
ptop++;
ed[ptop].v = u;
ed[ptop].flow = 0;
ed[ptop].cost = -cost;//反向路径费用为负
ed[ptop].i = ptop;
ed[ptop].nex = head[v];
head[v] = &ed[ptop];
ptop++;
}
int pre[M],newcost[N],Flow[N];
bool vis[N];
inline bool spfa(){
queue<int> qu;qu.push(s);vis[s] = 1;
memset(Flow,0,sizeof(Flow));Flow[s] = INF;//起点流量无限
memset(newcost,INF,sizeof(newcost));newcost[s] = 0;//起点费用为0
memset(pre,0,sizeof(pre));
while(!qu.empty()){
int u = qu.front();
qu.pop();
vis[u] = 0;
for(auto* p = head[u];p != NULL;p = p -> nex){
int v = p -> v;
if(p -> flow > 0 && newcost[v] > newcost[u] + p -> cost){//是否能更新这个点
newcost[v] = newcost[u] + p -> cost;//更新点的费用
Flow[v] = min(Flow[u],p -> flow);//更新流量
pre[v] = p -> i;//记录这条边
if(!vis[v]){vis[v] = 1,qu.push(v);}
}
}
}
return newcost[t] != INF;
}
void EK(){
while(spfa()){
ans1 += Flow[t],ans2 += newcost[t]*Flow[t];
int u = t;
while(u != s){
int k = pre[u];
ed[k].flow -= Flow[t];
ed[k^1].flow += Flow[t];
u = ed[k^1].v;
}
}
}
int main(){
cin >> n >> m >> s >> t;
for(int i = 1;i <= m;i++){
int u,v,flow,cost;
cin >> u >> v >> flow >> cost;
add(u,v,flow,cost);
}
EK();
cout << ans1 << ' ' << ans2 << endl;
}