网络流，费用流和二分图匹配模板

发表于 更新于 分类于

$\ \ \ \ \ \ \ \,$网络流，费用流相关的复习笔记：

网络流

Dinic

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
int head[N],p=1,S,T,n,m;
struct ss{int v,last,rl;}G[M<<1];
void add(int a,int b,int c){
	G[++p]=(ss){b,head[a],c};head[a]=p;
	G[++p]=(ss){a,head[b],0};head[b]=p;
}
int dis[N];
int bfs(int S,int T){
  memset(dis,0,sizeof(dis));
  queue<int> Q;dis[S]=1;Q.push(S);
  while(!Q.empty()){
    int u=Q.front();Q.pop();
    for(int i=head[u];i;i=G[i].last)
    if(G[i].rl>0&&dis[G[i].v]==0){
      dis[G[i].v]=dis[u]+1;
      Q.push(G[i].v);
    }
  }
  if(dis[T]!=0)return 1;
  else return 0;
}
int Augment(int a,int S,int T,int mi){
  if(a==T)return mi;
	int flow=0;
  for(int i=head[a];i;i=G[i].last)
  if((dis[G[i].v]==dis[a]+1)&&(G[i].rl!=0)){
    int ls=Augment(G[i].v,S,T,min(mi,G[i].rl));
		flow+=ls;mi-=ls;G[i].rl-=ls;G[i^1].rl+=ls;
    if(!mi)return flow;
  }
  return flow;
}
int Dinic(int S,int T){
	int ans=0,ls;
  while(bfs(S,T))ans+=Augment(S,S,T,inf);
  return ans;
}

ISAP

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
int head[N],p=1,S,T,n,m;
struct ss{int v,last;int rl;}G[M<<1];
void add(int a,int b,int c){
	G[++p]=(ss){b,head[a],c};head[a]=p;
	G[++p]=(ss){a,head[b],0};head[b]=p;
}
int dis[N],cur[N],num[N];
void bfs(int T){
	memset(dis,0,sizeof(dis));
	memset(num,0,sizeof(num));
	++num[dis[T]=1];
	memcpy(cur,head,sizeof(head));
	queue<int> Q;Q.push(T);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(int i=head[u];i;i=G[i].last)if(!dis[G[i].v])
		{++num[dis[G[i].v]=dis[u]+1];Q.push(G[i].v);}
	}
}
int Augment(int a,int S,int T,int mi){
	if(a==T)return mi;
	int flow=0;
	for(int i=cur[a];i;i=G[i].last)if(dis[G[i].v]==dis[a]-1){
		int ls=Augment(G[i].v,S,T,min(mi,G[i].rl));
		flow+=ls;mi-=ls;G[i].rl-=ls;G[i^1].rl+=ls;
		if(!mi)return flow;
	}
	if(!(--num[dis[a]]))dis[S]=n+1;
	++num[++dis[a]];cur[a]=head[a];
	return flow;
}
int ISAP(int S,int T){
	bfs(T);
	int ret=Augment(S,S,T,inf);
	while(dis[S]<=n)ret+=Augment(S,S,T,inf);
	return ret;
}

费用流（最小费用最大流）

ZKW

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
int head[N],p=1,S,T,n,m,k;
struct ss{int v,last;int rl,w;}G[M<<1];
void add(int a,int b,int c,int d){
	G[++p]=(ss){b,head[a],c,d};head[a]=p;
	G[++p]=(ss){a,head[b],0,-d};head[b]=p;
}
queue<int> Q;
int dis[N],Mincost,Maxflow;
bool used[N];
bool vis[N];
bool SPFA(int S,int T){
	for(int i=0;i<N;i++)dis[i]=inf,vis[i]=0;
	dis[T]=0,vis[T]=1;
	Q.push(T);
	while(!Q.empty()){
		int u=Q.front();Q.pop();vis[u]=0;
		for(int i=head[u];i;i=G[i].last)
		if(G[i^1].rl>0&&dis[G[i].v]>dis[u]-G[i].w){
			dis[G[i].v]=dis[u]-G[i].w;
			if(!vis[G[i].v])
			Q.push(G[i].v),vis[G[i].v]=1;
		}
	}
	return dis[S]<inf;
}
int Augment(int a,int S,int T,int mi){
	used[a]=1;
	if(a==T)return mi;
  int flow=0;
  for(int i=head[a];i;i=G[i].last)
	if(!used[G[i].v]&&G[i].rl&&dis[a]-G[i].w==dis[G[i].v]){
	  int ls=Augment(G[i].v,S,T,min(G[i].rl,mi));
	  Mincost+=ls*G[i].w,mi-=flow,G[i].rl-=ls,G[i^1].rl+=ls,flow+=ls;
	  if(!mi)return flow;
  }
  return flow;
}
void ZKW(int S,int T){
	Maxflow=Mincost=0;
	while(SPFA(S,T)){
		used[T]=1;
    while(used[T]){
      memset(used,0,sizeof(used));
      Maxflow+=Augment(S,S,T,inf);
    }
	}
}

二分图匹配

Hungary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool used[N<<1];
int n,m,e,ans;
int head[N],p;
struct ss{int v,last;}G[N*N];
void add(int a,int b)
{G[++p].v=b;G[p].last=head[a];head[a]=p;}
int match[N<<1];
bool dfs(int u){
	for(int i=head[u];i;i=G[i].last)if(!used[G[i].v]){
		used[G[i].v]=1;
		if(!match[G[i].v]||dfs(match[G[i].v]))
		{match[G[i].v]=u;return 1;}
	}
	return 0;
}
int Hungary(int n){
	int ans=0;
	for(int i=1;i<=n;i++){
		memset(used,0,sizeof(used));
		if(dfs(i))ans++;
	}
	return ans;
}

Kuhn Munkres（带权）

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
int head[N],p;
struct ss{int v,last,w;}G[N*N];
void add(int a,int b,int c)
{G[++p].v=b;G[p].last=head[a];G[p].w=c;head[a]=p;}
bool usem[N<<1],usen[N<<1];
int match[N<<1];
int maxn[N<<1],maxm[N<<1];
int slack[N<<1];
bool dfs(int u){
  usen[u]=1;
  for(int i=head[u];i;i=G[i].last){
    if(usem[G[i].v])continue;
    int gap=maxn[u]+maxm[G[i].v]-G[i].w;
    if(gap==0){
      usem[G[i].v]=1;
      if(match[G[i].v]==0||dfs(match[G[i].v]))
			{match[G[i].v]=u;return 1;}
    } 
		else slack[G[i].v]=min(slack[G[i].v],gap);
  }
  return 0;
}
int Kuhn_Munkres(int n){
	memset(match,0,sizeof(match));
	memset(maxm,0,sizeof(maxm));
	for(int u=1;u<=n;u++){
		maxn[u]=-inf;
		for(int i=head[u];i;i=G[i].last)
		maxn[u]=max(maxn[u],G[i].w);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)slack[j]=inf;
		while(1){
			memset(usem,0,sizeof(usem));
			memset(usen,0,sizeof(usen));
			if(dfs(i))break;
			int a=inf;
      for(int j=1;j<=m;j++)
      if(!usem[j])a=min(a,slack[j]);
      for(int j=1;j<=n;j++)
        if(usen[j])maxn[j]-=a;
      for(int j=1;j<=m;j++)
        if(usem[j])maxm[j]+=a;
		}
	}
	int res=0;
  for(int u=1;u<=n;u++){
		for(int i=head[u];i;i=G[i].last)
		if(match[G[i].v]==u)
		res+=G[i].w;
	}
  return res;
}