二分图的最小顶点覆盖

定义：假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。

方法：最小顶点覆盖等于二分图的最大匹配。

我们用二分图来构造最小顶点覆盖。

二分图的最大独立集

定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。

方法：最大独立集=所有顶点数-最小顶点覆盖。

二分图的最大团

定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。

方法：二分图的最大团=补图的最大独立集。

补图的定义是：对于二分图中左边一点x和右边一点y，若x和y之间有边，那么在补图中没有，否则有。

这个方法很好理解，因为最大独立集是两两不相邻，所以最大独立集的补图两两相邻。

最小边覆盖

边覆盖集：通俗地讲，所谓边覆盖集，就是G中所有的顶点都是E中某条边的邻接顶点（边覆盖顶点），一条边只能覆盖2个顶点。

注意：在无向图中存在用尽量少的边去“覆盖”住所有的顶点，所以边覆盖集有极小与最小的区别。

极小边覆盖：若边覆盖E中的任何真子集都不是边覆盖集，则称E是极小边覆盖集。

最小边覆盖：边数最小的边覆盖称为最小边覆盖，通俗地讲，就是极小边覆盖中的最小的一个集合。

最小边覆盖 = 最大独立集 = n - 最大匹配

最大权闭合子图

定义：有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。

方法：将正权点连接s,容量为点权,负权点连接t容量为点权绝对值,所求得的最小割将图分为两部分,我们发现所有正点权的和减去该简单割便是与s相连的闭合图的权，通过最小割找到了最大权闭合图。

最大密度子图

定义：给定一个无向图，要求它的一个子图，使得子图中边数 与点数 的比值最大，

方法：定义$d_i$为与点i相连的所有边的权值和，定义$p_i$为点i的权，保留以前的图，新建源点s汇点t，s到i连边，权值为U，i到t连边，权值为$2g-d_i-2p_i$

那么$h(g)$的值为$(U\cdot n-maxflow)$，二分答案就行了。

最小路径覆盖子图

定义：对于一个有向图，找出最小的路径条数，使之成为一个路径覆盖．

方法：用原图建立一个两层的新图，如果原图中存在边i->j我们建立的新图就有第一层的点i流到第二层的点j，最后建立超级源点流向 所有的第一层图的点，建立超级汇点，由所有第二层的图流入，用n减去所 求的最大流就是最小路径。

有向无环图最长链、最长反链

在有向无环图中，有如下的一些定义和性质：

链：一条链是一些点的集合，链上任意两个点x, y，满足要么 x 能到达 y ，要么 y 能到达 x 。

反链：一条反链是一些点的集合，链上任意两个点x, y，满足 x 不能到达 y，且 y 也不能到达 x。

一个定理：最长反链长度=最小链覆盖（用最少的链覆盖所有顶点）

对偶定理：最长链长度=最小反链覆盖

最小链覆盖（可以相交的最小路径覆盖）（最长反链长度）（用最少的链覆盖所有顶点）

定义：一条链是一些点的集合，链上任意两个点x, y，满足要么 x 能到达 y ，要么 y 能到达 x 。有向无环图中，找出最小的路径条数，使之成为的一个路径覆盖。

方法：我们将原图做一次Floyd传递闭包，在新图中寻找最小路径覆盖，这样其实就是相当于将原图改造了一下，只要 x 能到达 y ，就直接连一条边 (x, y)，这样就可以“绕过”原图的一些被其他路径占用的点，直接构造新路径了。这样就将可以相交的最小路径覆盖转化为了路径不能相交的最小路径覆盖了。

最大团 = 补图的最大独立集

最小边覆盖 = 二分图最大独立集 = |V| - 最小路径覆盖

最小路径覆盖 = |V| - 最大匹配数

最小顶点覆盖 = 最大匹配数

最小顶点覆盖 + 最大独立数 = |V|

最小割 = 最小点权覆盖集 = 点权和 - 最大点权独立集

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
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define per(i,j,k) for(int i=j;i>=(k);--i)
#define repe(i,u) for(int i=head[u];i;i=nex[i])

// graph
const int V=5e4+5,E=5e4+5;
int head[V];
int to[E],nex[E],ew[E],tot=1;
inline void addedge1(int u,int v,int w) {to[++tot]=v,nex[tot]=head[u],ew[tot]=w,head[u]=tot;}
void del(int u){repe(i,u) head[u]=0,del(to[i]);}

//最大流最小割算法
int lv[V],current[V],src,dst;
int *cap=ew;//容量等于边权
bool maxflowbfs(){
    queue<int>q;
    lv[src]=0, q.push(src);
    while(!q.empty()){
        int u=q.front();q.pop();
        repe(i,u){
            if(cap[i]==0||lv[to[i]]>=0)continue;
            lv[to[i]]=lv[u]+1, q.push(to[i]);
        }
    }
    return lv[dst]>=0;
}
int maxflowdfs(int u,int f){
    if(u==dst)return f;
    for(int&i=current[u];i;i=nex[i]){//当前弧优化
        if(cap[i]==0||lv[u]>=lv[to[i]])continue;
        int flow=maxflowdfs(to[i],min(f,cap[i]));
        if(flow==0) continue;
        cap[i]-=flow,cap[i^1]+=flow;
        return flow;
    }
    return 0;
}
ll maxflow(int base,int n,int s,int t){
    src=base+s,dst=base+t;
    ll flow=0,f=0;// 计算最大流的过程中不可能爆int 唯独在最后对流量求和对时候可能会比较大 所以只有这里用ll
    while(true){
        rep(i,base+1,base+n) current[i]=head[i],lv[i]=-1;
        if(!maxflowbfs())return flow;
        while(f=maxflowdfs(src,2e9))
            flow+=f;
    }
}