最大流与最小割

看了Amber神犇的论文《最小割模型在信息学竞赛中的应用》,感觉还是蛮系统的,我个人也写不出什么新东西,就对这篇论文进行摘要、简化,总结一下一些比较经典的最大流最小割算法和模型。

一些定义也不再赘述,具体的可以参考原论文。

我们知道,最大流与最小割是对偶问题,一个图的最小割也就是最大流量,一些模型的转化还是很显然的。

最大流算法

介绍比较实用的Dinic.
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
38
39
40
41
42
43
44
45
46
// Dinic 模板
int to[maxm],cur[maxm],head[maxm],next[maxm],wei[maxm],cnt;

void init(){
memset(head,-1,sizeof(head));
}

void insert(int u,int v,int w){
to[cnt]=v,wei[cnt]=w,next[cnt]=head[u],head[u]=cnt++;
to[cnt]=u,wei[cnt]=0,next[cnt]=head[v],head[v]=cnt++;
}

int d[maxn];
queue<int> q;
bool bfs(int s,int t){
memset(d,-1,sizeof(d));
q.push(s),d[s]=0;
while(!q.empty()){
int u=q.front(); q.pop();
for(int v=head[u];v>=0;v=next[v])
if(wei[v] && d[to[v]]<0) d[to[v]]=d[u]+1,q.push(to[v]);
}
return d[t]+1;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
int used=0;
for(int v=cur[u],k;v>=0;v=next[v])
if(wei[v] && d[to[v]]==d[u]+1){
k=dfs(to[v],t,min(flow-used,wei[v]));
used+=k;
wei[v]-=k;
wei[v^1]+=k;
if(used==flow) return flow;
}
if(!used) d[u]=-1;
return used;
}
int dinic(int s,int t){
int ans=0;
while(bfs(s,t)){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,t,inf);
}
return ans;
}

模型

二分图匹配

最大权闭合图

  • 实际情况 物品间有一些对应关系,每个物体有收入和支出,满足A所有的对应物品的支出才可获得A的收入,需要最大化收入
  • 建模方法 新建S,T,由S向物品连权值为收入的有向边,物品向T连权值为支出绝对值的有向边,对应关系连流量为正无穷的有向边
  • 建模分析 想象支出流流入物品,经过一些削减得到最终的支出,答案即为总获利-最大流
  • 例题
    · 最大获利 [BZOJ 1497]

二分图最小点权覆盖集

  • 实际情况 给定每个点的点权和连接他们的一些边,求一个权值最小的子点集使得对于图中的每条边,都有其中任意一个端点属于这个点集
  • 建模方法 新建S,T,分离物品为两个点a,b,由S向物品,物品向T连接一条为点权的有向边,在原图中有边的有a向b连一条容量为无限的有向边
  • 建模分析 实际上是求最小割,我们要保证有关系的a,b,S-a,b-T,至少有一个要被选,也就是要“割开”计入目标函数,我们又不能让a-b被割,所以设为正无穷,现在最小化割,也就是问题的求解
  • 应用 有向图的破坏
    定义:给出一个有向图,对于每个点,定义两种操作:操作1 删除此点的所有出边,花费代价ca;操作2 删除此点所有入边操作花费代价cb。求将原图的边集的边全部删除的最少代价
    解法:以为每条边都要删除,且只能被两种方法删,就很好的转化为最小点权覆盖集问题了

二分图最大点权独立集

  • 实际情况 给定每个点的点权和连接他们的一些边,求一个权值最大的子点集使得对于图中的每条边,两个端点不同时属于这个点集
  • 建模方法 同最小点权覆盖集
  • 建模分析 可以证明,覆盖集对点集的补集是一个独立集,当最小化了覆盖集的点权,也就同时最大化了独立集的点权
  • 例题
    · 王者之剑 [BZOJ 1324]

最小路径覆盖

  • 实际情况 给定有向图 G=(V,E)。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个顶点恰好在 P 的一条路上,则称 P 是 G 的一个路径覆盖。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。
  • 建模方法 分离顶点为a,b,S向a,b向T连正无穷,图中有关系的a,b连1
  • 建模分析 脑补一下是十分形象的

最大密集子图

· 补充知识 分数规划 (updating)

根据实际情况建图

  • 这就看自己的创造力辣~